7 6 5
8
1 2 1
2 3 1
3 4 1
3 5 100
4 5 1
5 6 100
6 7 1000
5 7 100
8
1 2 1
2 3 1
3 4 1
3 5 1
4 5 100
5 6 1
7 5 2
7 3 1000