6
2 1 10
3 1 15
1 4 5
4 5 12
4 6 8
0