10 15
0 1 100000000
0 2 100000000
1 2 1
1 3 100000000
2 3 100000000
3 4 100000000
3 5 100000000
4 5 1
4 6 100000000
5 6 100000000
6 7 100000000
6 8 100000000
7 8 1
7 9 100000000
8 9 100000000