9 60
1 2 1000
10 3 16
10 4 18
10 2 15
10 1 9
10 6 25
10 5 26
98 10000 1
55 100000 2