4 4
1 2 1000000000
2 3 1000000000
1 4 999999999
4 3 1000000000