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