3
3 2
1 2 40
2 3 20
7 10
1 1 1
1 2 2
2 4 2
4 3 2
3 1 2
2 3 5
3 7 10
7 6 1
5 6 1
4 5 1
16 15
1 8 1
2 8 1
3 8 1
4 9 1
5 9 1
6 9 1
7 8 1
8 9 3
9 10 1
8 11 1
8 12 1
8 13 1
9 14 1
9 15 1
9 16 1