problemas-para-competicao-pibiti-arthur-dolival/quase-menor-caminho/input/5

14 132
10 4
10 8 19
8 12 15
12 11 9
11 6 9
6 7 10
7 4 16
0 1 219
0 2 963
0 3 300
0 4 420
0 5 618
0 6 697
0 7 188
0 10 376
0 11 623
0 12 794
1 0 518
1 2 395
1 3 763
1 4 258
1 5 636
1 7 144
1 9 405
1 10 376
1 11 411
1 12 4
2 0 524
2 4 647
2 5 350
2 6 616
2 7 160
2 8 375
2 10 212
2 12 940
2 13 782
3 1 228
3 4 579
3 5 539
3 6 523
3 8 496
3 9 955
3 10 633
3 11 363
3 12 865
3 13 360
4 1 673
4 2 59
4 3 701
4 5 218
4 6 49
4 9 433
4 10 144
4 11 794
4 12 780
4 13 375
5 1 479
5 3 487
5 8 774
5 9 272
5 10 130
5 11 309
5 12 677
6 2 499
6 3 76
6 4 438
6 5 956
6 8 635
6 9 693
6 10 731
6 11 967
6 12 414
6 13 41
7 0 469
7 5 731
7 6 392
7 8 685
7 9 325
7 11 617
7 12 853
7 13 470
8 1 151
8 2 435
8 4 216
8 5 621
8 7 841
8 9 523
8 10 43
8 11 141
9 0 532
9 1 864
9 3 163
9 6 475
9 7 873
9 8 383
9 10 632
9 11 918
9 13 75
10 0 974
10 1 988
10 2 726
10 4 153
10 5 29
10 6 529
10 11 226
11 0 765
11 1 345
11 3 965
11 5 416
11 7 964
11 8 466
11 9 361
11 10 960
11 12 724
12 0 594
12 1 424
12 3 866
12 4 210
12 7 532
12 8 883
12 10 479
12 13 33
13 0 737
13 1 569
13 2 222
13 3 619
13 4 959
13 5 452
13 6 930
13 7 619
13 8 941
13 9 226
13 10 81
38 40
0 37
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
0 37 41
0 2 3
2 37 38
39 1351
2 33
2 27 15
27 14 13
14 8 12
8 12 12
12 3 18
3 1 15
1 26 10
26 37 12
37 18 12
18 24 2
24 0 19
0 22 7
22 5 8
5 30 20
30 15 9
15 28 11
28 10 16
10 33 4
0 1 111
0 2 432
0 3 181
0 4 720
0 5 371
0 6 135
0 7 870
0 8 413
0 9 944
0 10 286
0 11 237
0 12 732
0 13 41
0 14 392
0 15 577
0 16 625
0 17 627
0 18 778
0 19 187
0 20 669
0 23 809
0 24 288
0 25 31
0 27 778
0 28 123
0 29 549
0 30 922
0 31 81
0 32 843
0 34 224
0 36 724
0 37 16
0 38 73
1 0 213
1 2 658
1 3 165
1 4 296
1 5 869
1 6 29
1 7 449
1 8 820
1 9 547
1 10 18
1 11 550
1 12 739
1 14 380
1 15 431
1 16 543
1 18 599
1 19 89
1 20 663
1 22 915
1 23 19
1 24 856
1 25 380
1 27 112
1 28 907
1 29 762
1 30 600
1 31 409
1 32 888
1 33 708
1 35 764
1 36 994
1 37 283
1 38 683
2 0 931
2 3 40
2 4 61
2 5 887
2 6 529
2 7 70
2 8 554
2 9 32
2 10 706
2 11 458
2 12 761
2 13 313
2 14 551
2 15 483
2 16 559
2 17 632
2 18 603
2 19 146
2 20 891
2 21 555
2 22 660
2 23 734
2 24 926
2 25 245
2 26 275
2 28 687
2 29 45
2 30 829
2 31 307
2 32 131
2 33 257
2 34 716
2 35 27
2 37 916
2 38 648
3 0 100
3 2 114
3 4 61
3 6 89
3 7 29
3 9 619
3 10 771
3 11 390
3 12 733
3 13 550
3 15 55
3 17 583
3 18 872
3 19 889
3 20 216
3 21 2
3 22 937
3 23 709
3 25 801
3 26 339
3 27 200
3 28 778
3 29 958
3 31 84
3 32 3
3 33 981
3 34 679
3 36 615
3 37 643
3 38 698
4 1 448
4 2 453
4 3 129
4 6 187
4 7 157
4 8 127
4 9 941
4 10 694
4 11 716
4 12 750
4 13 791
4 14 91
4 16 790
4 17 614
4 18 806
4 19 337
4 20 179
4 21 739
4 22 373
4 23 136
4 24 893
4 25 614
4 26 161
4 27 759
4 28 949
4 29 827
4 30 129
4 32 198
4 33 57
4 34 953
4 35 107
4 36 525
4 37 733
4 38 269
5 0 166
5 2 906
5 3 274
5 4 821
5 6 229
5 8 118
5 9 331
5 10 540
5 12 139
5 13 223
5 14 414
5 15 70
5 16 424
5 17 106
5 18 125
5 19 253
5 20 305
5 22 339
5 23 537
5 24 42
5 25 939
5 26 283
5 27 10
5 28 341
5 29 25
5 31 739
5 32 16
5 34 10
5 36 148
5 37 51
5 38 908
6 0 958
6 1 751
6 3 307
6 4 530
6 5 478
6 7 220
6 8 459
6 9 664
6 10 943
6 11 920
6 12 448
6 13 107
6 14 769
6 16 911
6 17 858
6 18 733
6 19 236
6 20 87
6 21 310
6 22 851
6 23 722
6 24 358
6 25 291
6 26 951
6 27 978
6 28 638
6 29 920
6 30 20
6 31 303
6 32 630
6 33 660
6 34 232
6 35 115
6 36 525
6 37 773
6 38 462
7 0 551
7 1 931
7 2 881
7 4 984
7 5 416
7 6 186
7 8 962
7 9 611
7 10 794
7 11 817
7 12 957
7 13 549
7 14 703
7 15 536
7 16 293
7 17 636
7 18 740
7 20 938
7 22 679
7 23 360
7 24 931
7 25 526
7 26 451
7 27 655
7 28 655
7 30 611
7 31 638
7 32 989
7 33 514
7 34 612
7 36 955
7 37 538
7 38 533
8 0 927
8 1 69
8 2 619
8 3 372
8 4 57
8 5 511
8 6 288
8 7 757
8 9 154
8 11 270
8 13 794
8 14 972
8 15 862
8 16 168
8 17 378
8 19 766
8 20 797
8 22 916
8 23 26
8 24 920
8 26 832
8 27 965
8 28 183
8 29 141
8 30 145
8 31 18
8 32 771
8 33 630
8 34 832
8 35 408
8 36 316
8 37 366
8 38 255
9 0 151
9 1 661
9 2 76
9 3 981
9 4 124
9 5 855
9 6 354
9 7 252
9 8 492
9 10 242
9 11 152
9 12 76
9 13 384
9 14 955
9 15 1
9 16 452
9 17 823
9 18 397
9 19 610
9 21 171
9 22 132
9 23 565
9 24 741
9 26 390
9 27 229
9 28 803
9 29 409
9 30 412
9 31 467
9 32 662
9 33 624
9 34 504
9 35 766
9 37 298
9 38 707
10 0 435
10 1 591
10 2 819
10 3 944
10 4 501
10 5 286
10 8 417
10 11 637
10 12 479
10 13 943
10 15 813
10 17 607
10 18 282
10 19 581
10 20 871
10 21 627
10 22 899
10 23 376
10 24 503
10 25 567
10 26 148
10 27 143
10 28 473
10 29 82
10 30 996
10 31 967
10 32 657
10 34 996
10 35 832
10 36 519
10 37 461
10 38 921
11 0 162
11 1 165
11 2 383
11 3 654
11 4 367
11 5 918
11 6 225
11 8 716
11 9 8
11 10 769
11 12 55
11 13 442
11 14 445
11 16 463
11 17 69
11 18 815
11 19 818
11 20 387
11 21 307
11 22 363
11 23 91
11 24 108
11 25 302
11 26 812
11 28 72
11 29 635
11 30 266
11 31 980
11 32 107
11 33 874
11 34 586
11 35 663
11 37 22
11 38 884
12 0 979
12 1 462
12 4 549
12 5 212
12 6 800
12 7 725
12 8 718
12 9 312
12 10 344
12 11 423
12 13 29
12 14 32
12 15 532
12 16 107
12 17 80
12 18 675
12 19 732
12 20 247
12 21 126
12 22 108
12 23 748
12 24 586
12 25 576
12 26 586
12 27 350
12 28 413
12 29 752
12 30 168
12 31 186
12 32 101
12 33 331
12 34 14
12 35 267
12 36 918
12 37 644
13 0 576
13 1 844
13 2 738
13 3 551
13 4 715
13 5 195
13 7 681
13 8 405
13 9 360
13 10 139
13 11 501
13 12 326
13 14 653
13 15 753
13 16 531
13 17 308
13 18 358
13 19 667
13 20 479
13 21 23
13 22 353
13 23 91
13 24 348
13 25 649
13 26 380
13 27 42
13 28 815
13 29 189
13 30 526
13 31 941
13 32 640
13 33 867
13 34 68
13 35 599
13 37 269
13 38 210
14 0 691
14 1 258
14 2 40
14 3 240
14 4 529
14 5 490
14 6 433
14 7 910
14 9 681
14 10 322
14 11 117
14 12 971
14 15 827
14 16 305
14 17 706
14 18 94
14 19 542
14 20 813
14 21 49
14 22 903
14 23 335
14 24 671
14 25 327
14 26 746
14 28 546
14 29 920
14 30 248
14 31 913
14 33 89
14 34 300
14 35 862
14 36 371
14 37 71
14 38 663
15 0 878
15 1 335
15 2 821
15 3 994
15 4 196
15 5 132
15 6 207
15 7 669
15 8 314
15 9 583
15 10 801
15 11 984
15 12 612
15 13 330
15 14 507
15 16 136
15 19 902
15 20 176
15 21 622
15 22 28
15 23 390
15 24 334
15 25 312
15 26 805
15 27 24
15 30 633
15 31 483
15 32 567
15 33 316
15 34 171
15 35 544
15 36 724
15 37 907
15 38 539
16 0 352
16 1 368
16 2 674
16 3 698
16 5 308
16 6 867
16 7 408
16 8 987
16 9 229
16 10 108
16 12 488
16 13 169
16 14 972
16 15 387
16 17 338
16 18 641
16 19 856
16 22 385
16 24 909
16 26 583
16 27 374
16 28 687
16 29 527
16 30 630
16 31 636
16 32 889
16 33 893
16 34 61
16 35 698
16 36 726
16 38 445
17 0 765
17 1 579
17 2 388
17 3 595
17 4 207
17 5 724
17 6 117
17 7 182
17 8 242
17 9 639
17 11 800
17 12 921
17 13 472
17 14 996
17 15 828
17 16 942
17 18 589
17 19 944
17 20 149
17 21 936
17 22 291
17 23 692
17 24 520
17 25 804
17 26 495
17 27 241
17 28 200
17 29 417
17 30 329
17 31 943
17 32 632
17 33 948
17 34 321
17 35 214
17 36 717
17 37 635
17 38 888
18 0 674
18 2 896
18 3 516
18 4 305
18 5 158
18 6 654
18 7 68
18 8 314
18 9 457
18 10 165
18 11 106
18 12 268
18 13 290
18 14 786
18 15 607
18 16 354
18 17 779
18 19 151
18 20 864
18 21 380
18 22 368
18 23 288
18 25 407
18 26 661
18 27 147
18 28 508
18 29 476
18 30 634
18 32 804
18 33 40
18 35 238
18 36 856
18 37 548
18 38 155
19 0 64
19 1 176
19 2 723
19 3 18
19 4 701
19 5 683
19 6 757
19 7 967
19 9 17
19 10 502
19 11 547
19 12 597
19 13 831
19 14 126
19 15 460
19 16 590
19 17 752
19 18 572
19 20 848
19 21 693
19 22 326
19 23 820
19 24 3
19 25 324
19 27 396
19 28 842
19 29 155
19 31 542
19 32 276
19 33 927
19 34 337
19 35 754
19 36 935
19 38 995
20 0 217
20 1 857
20 2 653
20 3 733
20 4 380
20 5 404
20 6 756
20 7 176
20 8 459
20 9 330
20 10 272
20 12 244
20 13 402
20 14 323
20 15 313
20 16 198
20 17 460
20 18 388
20 19 131
20 21 285
20 22 534
20 23 136
20 24 169
20 25 301
20 27 871
20 28 226
20 29 534
20 30 85
20 31 215
20 32 48
20 33 371
20 34 322
20 36 807
20 37 406
20 38 329
21 0 281
21 1 408
21 2 668
21 3 175
21 4 99
21 5 388
21 6 280
21 7 662
21 8 122
21 9 157
21 10 901
21 11 11
21 12 980
21 13 109
21 14 537
21 15 729
21 16 691
21 17 497
21 18 869
21 19 986
21 20 820
21 23 420
21 24 347
21 25 858
21 26 362
21 27 219
21 28 482
21 29 295
21 30 521
21 31 258
21 32 687
21 33 297
21 34 685
21 35 203
21 36 69
21 37 227
21 38 882
22 0 452
22 1 633
22 2 561
22 4 688
22 6 43
22 7 92
22 8 424
22 9 138
22 10 25
22 11 79
22 12 137
22 13 413
22 14 213
22 15 793
22 16 158
22 17 879
22 18 177
22 19 755
22 20 119
22 21 80
22 23 361
22 24 907
22 25 563
22 26 772
22 27 783
22 28 969
22 29 975
22 30 904
22 31 466
22 32 818
22 33 510
22 34 333
22 35 594
22 36 250
22 37 635
22 38 283
23 0 473
23 1 58
23 2 977
23 3 570
23 4 645
23 5 420
23 6 564
23 7 998
23 8 423
23 10 457
23 11 986
23 12 314
23 13 8
23 14 624
23 15 21
23 16 635
23 17 483
23 18 86
23 19 922
23 20 665
23 21 897
23 22 364
23 25 667
23 26 506
23 27 704
23 28 809
23 29 290
23 30 361
23 32 827
23 33 572
23 34 571
23 35 257
23 36 194
23 37 438
23 38 96
24 1 408
24 2 16
24 3 882
24 4 162
24 5 702
24 6 124
24 7 367
24 8 724
24 9 276
24 10 828
24 11 348
24 12 404
24 14 337
24 16 812
24 17 669
24 18 938
24 19 53
24 20 53
24 21 519
24 22 724
24 23 63
24 25 297
24 26 793
24 27 205
24 29 274
24 30 216
24 31 939
24 32 223
24 33 225
24 34 635
24 36 425
24 37 89
24 38 258
25 0 775
25 1 116
25 2 511
25 3 707
25 4 505
25 5 628
25 6 982
25 7 728
25 8 34
25 9 714
25 10 11
25 12 640
25 13 413
25 14 996
25 15 746
25 16 739
25 17 105
25 18 689
25 19 159
25 21 498
25 22 238
25 23 460
25 24 350
25 26 271
25 28 124
25 29 235
25 30 415
25 31 462
25 32 373
25 33 420
25 34 888
25 35 380
25 36 56
25 37 433
25 38 749
26 0 928
26 1 440
26 2 21
26 3 217
26 4 629
26 5 608
26 6 706
26 7 413
26 9 198
26 10 197
26 11 193
26 12 47
26 13 666
26 14 245
26 15 922
26 16 536
26 17 982
26 18 817
26 19 581
26 20 614
26 21 443
26 22 820
26 23 45
26 24 166
26 25 72
26 27 376
26 28 645
26 29 455
26 30 290
26 31 29
26 32 683
26 33 905
26 34 847
26 35 484
26 36 69
26 38 614
27 0 862
27 1 329
27 2 959
27 3 431
27 4 915
27 5 231
27 6 831
27 7 944
27 8 19
27 9 263
27 10 294
27 11 260
27 12 310
27 13 988
27 15 999
27 16 101
27 17 818
27 18 881
27 19 655
27 20 557
27 22 957
27 23 996
27 24 590
27 25 917
27 26 303
27 28 211
27 29 882
27 30 684
27 31 943
27 33 632
27 34 156
27 35 966
27 36 461
27 37 414
27 38 833
28 1 611
28 2 802
28 3 692
28 4 357
28 5 815
28 7 822
28 8 991
28 9 22
28 11 493
28 12 125
28 13 692
28 14 527
28 15 530
28 16 62
28 17 470
28 18 785
28 19 838
28 20 980
28 21 671
28 22 626
28 23 848
28 24 376
28 25 730
28 26 775
28 27 724
28 29 258
28 30 672
28 31 362
28 32 201
28 33 251
28 34 45
28 35 305
28 36 770
28 38 789
29 0 330
29 1 334
29 2 467
29 3 29
29 4 216
29 5 995
29 6 308
29 7 688
29 8 528
29 9 743
29 10 779
29 11 932
29 12 716
29 13 145
29 14 67
29 15 787
29 17 904
29 18 624
29 19 938
29 20 75
29 21 922
29 23 599
29 24 61
29 25 715
29 26 676
29 27 188
29 28 223
29 30 278
29 31 197
29 32 498
29 33 668
29 34 13
29 35 961
29 37 450
29 38 953
30 0 621
30 1 674
30 2 534
30 3 20
30 4 143
30 5 990
30 6 942
30 7 163
30 8 338
30 9 476
30 10 302
30 11 346
30 12 423
30 14 166
30 16 959
30 18 836
30 19 778
30 20 964
30 21 345
30 22 527
30 23 621
30 24 467
30 25 650
30 26 56
30 27 317
30 29 630
30 31 798
30 32 274
30 33 272
30 34 755
30 35 928
30 36 565
30 37 631
30 38 969
31 0 202
31 1 11
31 2 228
31 3 771
31 4 427
31 5 829
31 6 613
31 7 930
31 8 388
31 10 692
31 11 875
31 12 267
31 13 773
31 14 732
31 16 192
31 17 842
31 18 930
31 19 319
31 20 819
31 21 807
31 22 291
31 23 250
31 24 71
31 25 841
31 26 43
31 27 45
31 28 645
31 29 504
31 30 194
31 33 590
31 34 514
31 35 154
31 36 931
31 38 917
32 0 122
32 1 483
32 3 420
32 4 842
32 5 307
32 6 210
32 7 925
32 8 231
32 9 340
32 10 674
32 11 934
32 12 988
32 13 776
32 14 784
32 15 332
32 17 495
32 18 733
32 19 853
32 20 763
32 22 845
32 23 199
32 25 431
32 27 114
32 28 742
32 29 800
32 30 499
32 31 704
32 33 208
32 34 122
32 35 405
32 36 165
32 37 639
32 38 806
33 0 299
33 1 581
33 2 97
33 3 844
33 4 800
33 5 320
33 6 655
33 7 815
33 9 977
33 10 759
33 11 191
33 12 216
33 13 545
33 14 364
33 15 337
33 16 83
33 17 884
33 18 598
33 20 29
33 21 194
33 22 3
33 23 507
33 24 299
33 25 671
33 26 168
33 27 566
33 28 90
33 29 807
33 30 644
33 31 95
33 32 411
33 34 421
33 35 651
33 36 893
33 37 178
33 38 339
34 0 950
34 1 684
34 2 414
34 3 890
34 4 365
34 5 183
34 6 13
34 7 701
34 8 7
34 9 757
34 10 715
34 11 173
34 12 460
34 13 487
34 14 782
34 15 661
34 16 20
34 17 647
34 18 795
34 20 509
34 21 9
34 22 867
34 23 469
34 24 594
34 25 297
34 26 51
34 27 424
34 28 227
34 29 498
34 30 447
34 31 839
34 32 793
34 33 441
34 35 46
34 36 84
34 37 441
34 38 21
35 0 17
35 1 832
35 3 533
35 4 36
35 6 797
35 7 153
35 8 386
35 9 836
35 10 531
35 11 932
35 12 314
35 13 29
35 14 603
35 15 474
35 16 614
35 17 899
35 18 227
35 19 775
35 20 857
35 21 230
35 23 943
35 24 134
35 25 77
35 26 739
35 27 49
35 28 353
35 29 575
35 30 390
35 31 57
35 32 53
35 33 673
35 34 680
35 36 3
35 37 816
35 38 793
36 0 203
36 1 305
36 2 699
36 3 707
36 4 762
36 5 485
36 6 300
36 7 781
36 8 982
36 9 437
36 10 790
36 11 505
36 12 545
36 14 209
36 15 704
36 16 886
36 18 281
36 19 656
36 20 128
36 21 85
36 23 940
36 24 939
36 25 897
36 26 175
36 27 626
36 28 471
36 29 879
36 30 152
36 31 905
36 33 383
36 34 271
36 35 887
36 37 971
37 0 165
37 1 139
37 2 868
37 3 804
37 4 575
37 5 451
37 6 210
37 7 570
37 8 942
37 9 692
37 11 284
37 12 290
37 13 543
37 14 275
37 15 164
37 16 247
37 17 79
37 19 780
37 20 338
37 21 464
37 22 154
37 23 834
37 24 885
37 25 656
37 27 137
37 28 748
37 29 176
37 30 613
37 31 802
37 32 966
37 33 601
37 34 492
37 35 791
37 36 780
37 38 332
38 1 347
38 2 741
38 3 229
38 4 37
38 5 833
38 6 573
38 7 878
38 9 805
38 11 505
38 12 5
38 13 433
38 14 934
38 15 338
38 16 210
38 17 583
38 18 357
38 19 805
38 20 982
38 21 678
38 22 499
38 24 698
38 25 854
38 26 312
38 27 75
38 29 219
38 30 971
38 31 785
38 33 963
38 34 802
38 35 341
38 36 131
0 0