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