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