9 1 8
9
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
9
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