5 10
1 2 4831
1 3 1023
1 4 1075
1 5 4002
5 2 1752
3 2 2603
5 1 4295
5 1 3468
4 1 2262
2 1 4292