6
1 2 10
1 5 2
2 3 1
2 4 8
3 6 3
4 1 5
4 3 16
5 4 4
5 6 7
6 4 5