5
2
1 2 100
1 3 10
1 4 100
1 5 300
3 1 10
2 3 100
2 4 10
2 5 300
3 4 47
3 5 27
1 3 56
4 5 74
2 1 100
0 0 0