3
1 2 300
2 3 400
0 0 0
6
1 2 10
1 3 20
5 2 4
3 4 7
6 5 30
2 6 50
4 5 7
4 6 9
0 0 0
0