题目描述
Snuke 的城镇有地铁行驶，地铁线路图包括 N 个站点和 M 个地铁线。站点被从 1 到 N 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。
第 i 条线路( 1≤i≤M )是直接连接 pi 与 qi 的双向铁路，中间不存在其他站点，且这条铁路由 ci 公司所拥有。
如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。
Snuke在1号站的位置出发，他想通过地铁去第 N 站，请求出最小钱数。如果无法到达第 N 站，输出-1。
输入输出格式
输入格式
第一行，输入 N , M
接下来的 M 行，输入 pi qi ci ，代表 pi 与 qi 中间有直接连接的双向边，且这条铁路由 ci 公司所拥有。
输出格式
输出最小钱数（若无法到达，输出 −1）
3 3
1 2 1
2 3 1
3 1 2
1
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
2 0
-1
提示
- 2 ≤ N ≤ 105
- 0 ≤ M ≤ 2×105
- 1 ≤ pi ≤ N (1 ≤ i ≤ M)
- 1 ≤ qi ≤ N (1 ≤ i ≤ M)
- 1 ≤ ci ≤ 106 (1 ≤ i ≤ M)
- pi = qi (1 ≤ i ≤ M)
