7 4
1 2 29
2 3 7
2 4 94
4 5 81
4 6 9
6 7 60
1 2 4
1 4 3
1 2 7
1 6 3