9 8 1
12
1 2 1
2 3 1
3 4 1
4 5 1
3 8 100
8 9 1
5 6 1
6 7 1
7 8 1
1 9 1000
4 7 1000
5 8 1000
11
1 2 1
2 3 1
3 4 100
4 5 1
5 6 1
6 7 1
7 8 1
8 3 100
3 9 1
4 7 1000
3 6 1000