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