input.txt

10 2
104
40 325 8177 1345 1412 1020 1125 1076 1801 1368 1514 1848 1219
17 434 8539 1290 1549 1045 1014 1749 1970 1442 1918 1271 1896
33 412 5641 1799 1015 1888 1651 1498 1995 1336 1384 1392 1788
46 491 9206 1136 1824 1532 1177 1104 1619 1399 1622 1612 1608
65 371 7413 1435 1912 1623 1401 1731 1678 1636 1997 1536 1217
75 436 6161 1628 1327 1896 1049 1125 1911 1619 1655 1912 1729
3 419 5809 1108 1581 1978 1533 1138 1624 1323 1856 1656 1610
9 292 6277 1686 1353 1419 1353 1954 1319 1117 1716 1054 1145
15 262 6273 1629 1681 1210 1191 1417 1656 1084 1200 1856 1478
32 448 6335 1466 1717 1861 1720 1295 1718 1936 1511 1578 1050
20 380 -1
29 229 -1
35 321 -1
49 433 -1
54 321 -1
62 343 -1
67 403 -1
68 244 -1
69 200 -1
74 450 -1
79 267 -1
86 206 -1
81 278 -1
83 404 -1
84 498 -1
85 393 -1
101 350 -1
87 345 -1
94 365 -1
0 213 -1
4 366 -1
1 235 -1
2 445 -1
8 319 -1
6 365 -1
5 299 -1
19 341 -1
11 278 -1
7 375 -1
12 468 -1
13 266 -1
10 230 -1
16 327 -1
14 204 -1
22 347 -1
24 287 -1
18 398 -1
23 268 -1
28 402 -1
25 393 -1
21 335 -1
26 441 -1
30 406 -1
31 247 -1
37 417 -1
41 337 -1
43 431 -1
34 318 -1
45 385 -1
48 287 -1
36 372 -1
50 467 -1
53 322 -1
56 296 -1
52 202 -1
61 499 -1
55 444 -1
57 341 -1
58 329 -1
59 312 -1
60 223 -1
64 425 -1
63 308 -1
66 441 -1
78 481 -1
77 497 -1
80 491 -1
70 372 -1
76 404 -1
71 265 -1
72 289 -1
73 434 -1
82 491 -1
88 260 -1
93 437 -1
98 276 -1
100 268 -1
96 494 -1
97 449 -1
99 284 -1
102 371 -1
27 217 -1
38 435 -1
39 383 -1
44 421 -1
42 260 -1
47 485 -1
51 400 -1
91 262 -1
90 455 -1
89 339 -1
92 374 -1
95 457 -1
103 335 -1
116
0 4 306
0 3 244
1 2 253
1 8 228
2 3 292
3 9 346
4 6 210
5 19 228
5 15 209
6 11 347
7 8 344
7 12 345
9 13 209
9 17 422
10 15 274
10 16 480
11 14 247
12 17 494
13 32 276
14 22 476
15 20 340
16 24 406
17 18 306
17 23 416
18 27 495
19 28 476
20 25 253
20 33 269
21 26 418
21 30 246
22 31 306
23 29 332
24 25 232
26 35 411
28 40 406
29 35 345
29 38 408
30 37 467
31 32 222
32 39 475
33 41 439
33 43 297
33 44 464
34 45 495
34 48 277
35 36 243
36 40 302
37 40 339
40 41 489
40 43 452
40 46 274
42 49 246
45 65 463
46 47 488
46 49 243
46 50 381
48 53 327
49 56 491
50 52 345
51 61 340
52 55 385
53 54 380
54 65 377
54 57 340
55 58 427
56 75 405
57 59 356
58 60 321
59 64 322
60 62 250
61 65 203
62 65 238
62 67 277
63 67 454
63 68 443
64 69 300
66 68 268
66 78 303
67 74 410
68 77 353
69 79 247
69 80 454
70 86 480
70 76 237
71 74 485
71 81 305
72 75 251
72 73 353
73 77 277
74 83 260
75 91 442
75 78 241
76 79 491
79 86 384
80 81 493
81 82 325
82 84 201
83 84 231
83 85 302
84 88 307
85 101 404
85 87 467
86 93 292
87 90 463
87 94 237
88 89 404
92 93 288
94 98 243
94 100 330
95 96 424
96 97 482
97 99 274
98 102 262
99 100 356
101 103 219
101 102 482