2
4 3
0 1 100
1 2 10
0 3 30
3
1 2 3
220
17 19
0 1 10
1 2 10
2 3 10
3 4 10
4 14 10
14 15 10
15 16 10
16 0 10
2 5 11
5 6 10
6 7 10
7 8 10
8 9 10
9 2 11
7 10 11
10 11 10
11 12 10
12 13 10
13 7 11
5
3 7 10 11 12
157
