5 10
1 2 2863
1 3 2123
3 4 1637
4 5 1429
5 2 4653
3 1 4861
4 3 3825
3 2 4951
5 3 1075
3 2 4108