4 6
1 2 1000000000
1 3 1000000000
2 4 1000000000
2 3 1
3 4 1000000000
3 2 1