暂无测试数据。

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

输入格式

第一行两个整数分别表示 $n,m$

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

输出格式

输出 DD 的最少花费是多少

数据范围

对于 $30\%$ 的数据， $n \leq 100,c \leq 100$

对于另外 $20\%$ 的数据， $n \leq 10^5,c \leq 1$

对于 $100\%$ 的数据， $n,c \leq 10^5,m \leq 2 \times 10^5$

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

2