3
6 7
1 2 1
2 3 1
3 6 1
1 4 10
4 3 10
2 5 10
5 6 10
2
2 3
5 5
1 2 1
1 3 2
2 4 1
3 4 2
4 5 1
1
2
5 5
1 2 1
1 3 2
2 4 1
3 4 2
4 5 1
1
4