3
6
1 3 10
4 5 10
3 4 10
4 6 20
2 3 30
6
1 3 35
4 5 10
3 4 10
4 6 20
2 3 30
5
1 3 1000000000
2 3 1000000000
3 4 1000000000
3 5 1000000000