2000 6
1 2 2
3 4 10000
4 5 10000
5 3 10000
1 5 10000
2 2000 5