12 17
0 1 100000000
0 2 100000000
0 3 100000000
0 4 100000000
0 5 100000000
1 7 15
2 9 4
3 6 31
3 8 2
4 9 8
4 10 20
5 8 8
6 11 100000000
7 11 100000000
8 11 100000000
9 11 100000000
10 11 100000000