4 5 
1 2 3 
1 3 5 
1 4 6 
2 4 6 
3 4 7 
4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 
2 1 
1 2 1 
3 0 
3 1 
1 2 1 
3 3 
1 2 2 
2 3 5 
1 3 6 
5 10 
1 2 110 
1 3 120 
1 4 130 
1 5 120 
2 3 110 
2 4 120 
2 5 130 
3 4 120 
3 5 110 
4 5 120 
5 10 
1 2 9384 
1 3 887 
1 4 2778 
1 5 6916 
2 3 7794 
2 4 8336 
2 5 5387 
3 4 493 
3 5 6650 
4 5 1422 
5 8 
1 2 1 
2 3 100 
3 4 100 
4 5 100 
1 5 50 
2 5 50 
3 5 50 
4 1 150 
0 0