【样例1解释】
依次经过 1 号道路、2 号道路、3 号道路，并在经过 1、2 号道路前使用魔法。
【样例2解释】
依次经过 1 号道路、2 号道路、1 号道路，并在两次经过 1 号道路前都使用魔法。
【数据范围与提示】
对于所有测试点和样例满足：
1≤n≤100,1≤m≤2500,0≤K≤106,1≤ui,vi≤n,1≤ti≤1091≤n≤100,1≤m≤2500,0≤K≤106,1≤ui,vi≤n,1≤ti≤109
数据保证图中无自环，无重边，至少存在一条从 11 号城市到达 nn 号城市的路径。
每个测试点的具体限制见下表。
|
测试点编号
|
n≤n≤
|
m≤m≤
|
K≤K≤
|
特殊限制
|
|
1∼21∼2
|
55
|
2020
|
00
|
无
|
|
3∼43∼4
|
1010
|
2020
|
5050
|
无
|
|
5∼65∼6
|
1010
|
2020
|
00
|
无
|
|
7∼87∼8
|
2020
|
200200
|
5050
|
图中无环
|
|
9∼109∼10
|
2020
|
200200
|
00
|
无
|
|
11∼1211∼12
|
100100
|
200200
|
5050
|
图中无环
|
|
13∼1413∼14
|
100100
|
200200
|
5050
|
无
|
|
15∼1815∼18
|
100100
|
25002500
|
10001000
|
无
|
|
19∼2019∼20
|
100100
|
25002500
|
106106
|
无
|