C 城有 $n$ 个站点， $m$ 条双向地铁，每条地铁有一个 $company_i$ 表示它的公司，如果连续乘坐同一家公司的地铁只要花 $1$ 元钱就好。
DD 现在想出门找朋友玩，但是 DD 是贫困人口， 她想知道最少花费多少钱能从 $1$ 号点前往 $n$ 号点。

第一行两个整数分别表示 $n,m$。
接下来 $m$ 行每行 $3$ 个整数，分别表示地铁的起点终点和公司。

输出 DD 的最少花费是多少。

对于 $30\%$ 的数据，$n≤100,c≤100$。
对于另外 $20\%$ 的数据，$n \leq 10^5,c \leq 1$。
对于 $100\%$ 的数据，$n,c \leq 10^5,m \leq 2 \times 10^5$。

2

我们可以从 $1 \rightarrow 4 \rightarrow 8$。