AT_arc061_c [ARC061E] すぬけ君の地下鉄旅行

Snuke 的城镇有着复杂的地铁网络，共包括 $N$ 个站点和 $M$ 条地铁线。站点由 $1$ 到 $N$ 之间的整数编号。每条线路均属于某家公司，且每家公司用彼此不同的整数来表示。 具体而言，第 $i$ 条线路（$1\le i\le M$）是直接连接 $p_i$ 与 $q_i$ 的双向地铁线路，中间不存在其他站点，且这条地铁线路属于 $c_i$ 公司。 如果乘客只乘坐同一公司的地铁，他只需要花费一元，但如果他选择换乘其他公司的地铁，则需要再花一元。当然，如果他要再换回原来的公司，他还是要再花一元。 Snuke 当前在 $1$ 号站，他想通过乘坐地铁到达第 $N$ 站，请求出他需要花费的最小钱数。如果无法到达第 $N$ 站，输出 $-1$。

第一行，输入 $N,M$。 接下来的 $M$ 行，第 $i$ 行输入 $p_i,q_i,c_i$ ，代表编号为 $p_i$ 与 $q_i$ 的站点间有一条双向地铁线路，且这条线路属于 $c_i$ 公司。

输出 Snuke 需要花费的最小钱数。如果无法到达，输出 $-1$。

#### 数据范围 - $2 \leq N \leq 10^5$。 - $0 \leq M \leq 2×10^5$。 对于所有的 $1\le i\le M$，有 - $1 \leq p_i,q_i \leq N$。 - $1 \leq c_i \leq 10^6$。 - $p_i \neq q_i$。