8 10 2 20
1 2 990
1 3 784
1 4 406
1 5 866
1 6 171
1 7 129
1 8 826
2 8 1000000000
2 5 497
4 5 224
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1
1 2
1 2
1 2
2 1
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2