5 10
1 2 113400
1 3 131040
1 4 131040
1 5 126000
2 3 131040
2 4 90720
2 5 138600
3 4 110880
3 5 110880
4 5 95760