5 10
1 2 3355
2 3 1712
1 4 4892
1 5 1442
5 3 4768
3 1 4334
2 1 4365
3 1 2591
2 1 3817
3 2 4068