3
9 10
1 2 1
3 1 3
3 5 4
4 3 3
7 8 4
6 3 1
2 7 7
4 9 1
4 1
1 2 1
2 3 1
3 4 1
5 1000000000
2 1 1000000000
1 5 10
3 1 1
4 2 1000000000
