5 7
1 2 10
1 3 19
2 4 21
4 5 9
1 5 16
5 3 22
1 4 34
2
1 2 1
3 5 4