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

8 44
6 1
6 5 11
5 0 8
0 4 3
4 3 16
3 1 15
0 1 320
0 2 420
0 5 562
0 6 796
0 7 278
1 0 850
1 2 812
1 3 82
1 4 286
1 5 248
1 6 276
2 0 326
2 1 912
2 5 482
2 6 936
2 7 957
3 0 458
3 4 538
3 5 859
3 6 71
3 7 735
4 1 244
4 2 981
4 7 908
5 1 270
5 3 414
5 4 305
5 6 105
5 7 526
6 0 396
6 1 250
6 2 649
6 3 761
6 4 675
6 7 284
7 2 972
7 3 885
7 4 329
7 5 67
32 216
0 31
0 1 1
0 10 1
1 21 2
10 21 2
21 31 2
0 31 8
0 21 6
1 31 7
0 8 281
0 13 20
0 16 638
0 26 425
0 30 255
1 4 141
1 11 136
1 12 894
1 15 392
1 16 350
1 18 79
1 26 762
1 28 913
1 29 298
2 12 61
2 13 767
2 17 688
2 19 173
2 21 871
2 22 550
2 23 560
2 24 991
2 29 111
3 0 251
3 6 415
3 11 405
3 16 5
3 19 683
3 27 707
3 30 262
3 31 428
4 3 926
4 18 36
4 19 815
4 21 188
5 1 193
5 2 334
5 23 535
5 26 268
5 28 713
6 0 166
6 1 70
6 9 295
6 11 921
6 13 606
6 17 751
6 19 291
6 21 510
7 0 9
7 2 776
7 4 825
7 9 903
7 11 697
7 13 225
7 17 840
7 27 282
7 29 180
8 10 214
8 12 693
8 14 756
8 16 174
8 19 768
8 21 708
8 30 319
9 10 43
9 12 628
9 16 599
9 19 144
9 22 745
9 25 13
9 28 461
9 29 807
9 31 602
10 6 418
10 8 846
10 16 325
10 27 118
10 31 496
11 7 611
11 16 435
12 2 368
12 6 86
12 29 881
13 4 475
13 12 197
13 17 801
13 22 957
14 6 478
14 12 108
14 22 295
15 0 747
15 1 850
15 10 708
15 16 891
15 17 335
15 18 271
15 20 254
15 21 869
15 24 769
16 0 899
16 1 993
16 6 332
16 10 348
16 15 622
16 19 800
16 27 904
16 30 423
17 2 663
17 4 602
17 9 619
17 10 873
17 19 336
17 20 708
17 30 776
17 31 986
18 0 645
18 8 297
18 10 436
18 24 788
18 25 904
19 3 872
19 7 39
19 9 458
19 11 337
19 15 144
19 22 884
19 26 202
20 1 216
20 2 386
20 4 773
20 8 47
20 12 197
20 24 379
20 27 880
20 30 23
21 1 829
21 3 481
21 6 847
21 8 58
21 11 960
21 17 832
22 1 255
22 2 526
22 13 199
22 16 486
22 18 277
22 24 913
22 30 124
23 2 131
23 12 122
23 18 103
23 20 386
23 21 15
23 27 676
23 29 639
24 4 665
24 6 880
24 10 821
24 15 409
24 18 581
24 25 274
24 26 450
24 31 967
25 1 805
25 15 964
25 29 322
26 1 628
26 2 903
26 3 657
26 4 486
26 5 235
26 8 898
26 17 696
26 21 387
26 22 348
26 29 333
27 0 694
27 2 231
27 20 179
27 26 172
27 29 908
27 30 386
28 8 888
28 13 912
28 29 749
28 30 78
28 31 736
29 3 847
29 5 346
29 6 867
29 8 575
29 9 73
29 13 804
29 18 512
29 22 592
29 27 659
30 2 72
30 5 162
30 6 475
30 7 133
30 14 424
30 15 741
30 17 64
30 19 598
30 24 26
30 29 191
31 12 113
31 26 298
14 33
0 13
1 0 263
12 7 447
8 13 379
2 1 911
13 10 391
12 9 615
11 8 669
8 11 587
6 2 197
10 7 938
3 0 959
9 13 625
5 2 469
11 7 561
13 11 357
3 1 590
6 0 106
7 12 647
2 6 836
13 9 262
3 4 736
2 0 364
2 4 539
12 8 410
12 13 427
11 12 629
5 1 218
3 2 448
11 13 906
0 5 759
10 12 840
1 6 592
10 13 33
36 830
10 32
10 32 6
0 1 356
0 3 418
0 4 524
0 6 239
0 9 244
0 10 264
0 11 175
0 12 21
0 15 621
0 16 540
0 17 520
0 18 35
0 20 289
0 21 120
0 22 404
0 23 99
0 26 711
0 27 129
0 29 927
0 31 733
0 32 941
0 33 757
0 35 467
1 0 678
1 2 890
1 4 32
1 5 423
1 6 50
1 8 769
1 11 99
1 12 582
1 13 796
1 14 298
1 15 82
1 17 368
1 19 232
1 20 191
1 22 241
1 23 485
1 24 740
1 25 105
1 26 44
1 27 143
1 30 824
1 31 501
1 32 930
1 33 598
2 0 910
2 3 147
2 4 8
2 6 715
2 7 526
2 8 21
2 9 692
2 10 488
2 11 108
2 13 167
2 15 605
2 16 241
2 17 970
2 18 21
2 20 770
2 22 74
2 24 459
2 28 2
2 29 351
2 31 237
2 32 753
2 33 106
2 34 564
2 35 988
3 0 993
3 1 465
3 2 881
3 4 423
3 5 200
3 9 118
3 10 784
3 12 591
3 13 407
3 14 92
3 15 178
3 16 990
3 19 872
3 20 222
3 21 163
3 22 398
3 25 251
3 28 217
3 30 793
3 31 327
3 34 580
3 35 733
4 0 112
4 2 128
4 3 786
4 6 352
4 7 931
4 10 636
4 12 470
4 14 268
4 18 467
4 19 11
4 20 85
4 21 179
4 23 472
4 24 682
4 26 487
4 28 708
4 29 10
4 31 74
4 32 983
4 33 921
4 34 804
5 6 910
5 8 273
5 9 53
5 10 621
5 11 412
5 12 462
5 14 906
5 15 686
5 16 238
5 18 300
5 20 815
5 22 323
5 23 190
5 24 706
5 26 149
5 28 788
5 30 303
5 31 592
5 32 532
5 34 883
6 0 776
6 1 89
6 4 818
6 5 69
6 7 167
6 9 512
6 10 782
6 11 657
6 12 20
6 13 694
6 15 458
6 16 525
6 19 637
6 20 617
6 21 930
6 24 22
6 25 432
6 26 326
6 27 308
6 28 673
6 30 828
6 33 296
6 34 259
6 35 121
7 0 838
7 1 942
7 2 27
7 3 16
7 4 617
7 6 883
7 8 234
7 10 443
7 11 274
7 12 440
7 13 783
7 14 5
7 15 419
7 18 104
7 19 570
7 21 628
7 22 536
7 23 920
7 26 224
7 27 748
7 28 458
7 29 663
7 30 950
7 31 286
7 33 53
8 1 119
8 3 401
8 6 330
8 10 481
8 15 888
8 17 534
8 20 623
8 21 888
8 23 66
8 24 276
8 27 275
8 28 345
8 30 345
8 32 770
8 33 257
8 34 186
8 35 772
9 0 22
9 1 710
9 2 395
9 3 60
9 4 950
9 5 39
9 6 986
9 10 207
9 12 83
9 13 486
9 15 850
9 18 604
9 19 10
9 21 231
9 22 460
9 23 330
9 24 857
9 25 545
9 26 334
9 27 373
9 28 436
9 30 765
9 31 85
9 32 682
9 33 727
9 34 906
10 1 432
10 2 547
10 3 485
10 5 658
10 6 974
10 7 769
10 8 947
10 9 743
10 11 35
10 14 691
10 15 836
10 17 225
10 18 719
10 19 470
10 21 653
10 22 415
10 23 712
10 24 390
10 27 391
10 29 815
10 30 245
10 31 817
10 35 941
11 0 971
11 1 492
11 2 412
11 3 48
11 4 796
11 6 702
11 8 393
11 9 188
11 10 705
11 12 669
11 15 435
11 18 632
11 19 771
11 20 515
11 21 648
11 22 623
11 23 804
11 26 305
11 27 442
11 28 499
11 29 9
11 31 978
11 32 669
11 34 888
12 0 939
12 1 320
12 3 400
12 5 441
12 6 577
12 7 328
12 10 697
12 13 233
12 14 706
12 15 197
12 17 481
12 19 385
12 20 85
12 21 274
12 24 128
12 26 692
12 27 290
12 28 771
12 29 623
12 30 523
12 31 642
12 32 488
12 33 985
12 34 910
12 35 161
13 0 437
13 1 387
13 2 406
13 4 487
13 5 324
13 6 544
13 8 874
13 9 134
13 10 759
13 11 214
13 12 655
13 14 511
13 15 619
13 17 698
13 18 458
13 19 716
13 21 636
13 22 329
13 23 428
13 26 196
13 28 520
13 29 402
13 31 950
13 33 560
13 34 296
14 2 803
14 3 161
14 4 542
14 5 868
14 8 331
14 9 53
14 11 834
14 12 783
14 13 978
14 15 28
14 16 151
14 18 383
14 19 720
14 20 172
14 21 30
14 22 266
14 25 459
14 28 680
14 30 186
14 31 554
14 33 271
14 34 854
14 35 844
15 2 252
15 3 715
15 4 868
15 5 793
15 6 690
15 7 774
15 8 215
15 10 689
15 13 773
15 16 832
15 18 332
15 20 726
15 22 29
15 23 976
15 24 191
15 25 495
15 26 436
15 27 173
15 28 758
15 29 106
15 32 205
15 33 357
15 34 660
15 35 78
16 0 438
16 1 34
16 3 378
16 4 551
16 5 619
16 6 977
16 8 125
16 9 644
16 11 407
16 12 790
16 14 776
16 15 218
16 17 753
16 18 669
16 19 458
16 20 997
16 21 780
16 24 241
16 25 590
16 26 538
16 27 87
16 29 846
16 30 754
16 34 331
17 0 793
17 1 495
17 2 680
17 3 639
17 5 765
17 6 37
17 7 86
17 8 928
17 9 335
17 10 969
17 11 475
17 12 30
17 13 460
17 14 262
17 19 964
17 20 553
17 21 154
17 23 909
17 24 434
17 25 339
17 26 421
17 30 784
17 32 831
17 33 313
17 35 381
18 1 689
18 2 163
18 4 959
18 5 739
18 6 470
18 8 322
18 9 730
18 11 401
18 12 988
18 13 154
18 14 528
18 16 930
18 17 661
18 20 977
18 21 9
18 22 382
18 23 710
18 25 546
18 27 643
18 30 563
18 33 476
19 1 277
19 2 404
19 3 274
19 5 898
19 6 552
19 8 80
19 9 930
19 10 596
19 11 520
19 12 703
19 13 288
19 14 1000
19 15 771
19 16 391
19 18 680
19 20 369
19 23 581
19 24 496
19 26 750
19 27 535
19 29 4
19 30 448
19 32 174
19 33 323
20 0 26
20 1 371
20 2 349
20 4 23
20 5 456
20 6 412
20 7 541
20 14 960
20 16 206
20 22 681
20 23 292
20 25 964
20 26 135
20 27 394
20 28 437
20 29 909
20 30 66
20 31 801
20 32 911
20 33 182
20 34 641
21 1 556
21 3 608
21 7 269
21 8 573
21 9 84
21 10 847
21 11 229
21 12 797
21 13 18
21 15 248
21 16 6
21 17 332
21 20 858
21 22 338
21 23 756
21 24 174
21 25 966
21 26 622
21 27 541
21 28 382
21 29 818
21 30 633
21 32 136
21 34 186
21 35 678
22 0 506
22 1 174
22 2 971
22 3 834
22 4 249
22 5 384
22 6 257
22 7 409
22 8 805
22 9 189
22 10 436
22 11 423
22 12 629
22 13 440
22 15 80
22 16 455
22 18 528
22 20 982
22 21 508
22 23 574
22 26 147
22 28 595
22 29 977
22 30 445
22 31 25
22 32 314
22 33 221
22 35 285
23 1 356
23 2 199
23 3 518
23 4 424
23 7 365
23 8 694
23 9 200
23 10 21
23 11 758
23 12 725
23 13 76
23 14 260
23 15 93
23 16 936
23 18 594
23 19 956
23 20 33
23 21 898
23 24 837
23 26 427
23 27 655
23 28 874
23 29 830
23 31 981
23 32 939
23 34 583
23 35 87
24 0 386
24 1 722
24 2 421
24 3 651
24 5 490
24 6 209
24 7 902
24 8 216
24 9 677
24 11 691
24 12 405
24 13 921
24 14 302
24 15 559
24 16 105
24 17 761
24 19 570
24 20 969
24 21 325
24 25 707
24 26 927
24 27 914
24 30 44
24 31 366
24 32 519
24 33 888
24 35 280
25 2 295
25 3 805
25 9 983
25 11 228
25 12 381
25 14 1
25 15 270
25 16 371
25 17 644
25 18 550
25 19 705
25 20 959
25 21 40
25 22 995
25 24 129
25 28 355
25 29 101
25 30 80
25 31 255
25 33 252
25 34 217
25 35 184
26 0 960
26 1 607
26 2 325
26 5 640
26 7 945
26 8 297
26 10 540
26 11 440
26 13 679
26 16 613
26 17 942
26 18 434
26 19 229
26 20 791
26 21 809
26 23 636
26 24 246
26 27 398
26 28 724
26 30 40
26 32 800
26 33 103
26 35 21
27 0 982
27 2 455
27 4 72
27 7 608
27 8 322
27 9 822
27 11 636
27 13 871
27 14 365
27 15 952
27 17 279
27 18 346
27 19 551
27 21 827
27 22 626
27 25 155
27 26 319
27 29 488
27 31 307
27 32 180
27 35 255
28 1 317
28 2 236
28 3 429
28 4 384
28 7 293
28 8 595
28 10 96
28 11 273
28 16 446
28 18 61
28 21 789
28 23 807
28 24 201
28 26 627
28 29 991
28 32 714
28 33 588
28 35 609
29 0 778
29 1 777
29 4 571
29 5 359
29 6 722
29 8 481
29 9 477
29 11 491
29 12 547
29 14 527
29 15 273
29 16 667
29 17 1
29 20 841
29 23 785
29 25 94
29 27 506
29 28 940
29 31 383
29 32 114
29 33 207
29 34 22
29 35 573
30 1 421
30 2 420
30 3 749
30 4 313
30 5 562
30 6 629
30 7 922
30 8 556
30 9 383
30 12 125
30 13 691
30 14 158
30 15 800
30 16 889
30 19 119
30 20 545
30 23 127
30 24 161
30 25 593
30 26 827
30 27 968
30 28 410
30 33 434
30 34 833
30 35 525
31 2 184
31 5 574
31 7 389
31 8 170
31 9 562
31 11 345
31 12 342
31 14 432
31 16 741
31 17 155
31 18 17
31 19 84
31 20 232
31 21 565
31 22 342
31 23 163
31 26 498
31 27 253
31 28 44
31 30 297
31 32 689
31 33 56
31 34 803
32 3 45
32 4 313
32 5 766
32 8 396
32 13 996
32 16 624
32 17 724
32 18 46
32 19 143
32 20 336
32 21 775
32 22 955
32 23 899
32 24 328
32 28 315
32 31 548
32 33 975
32 34 460
33 0 894
33 2 873
33 3 654
33 6 745
33 7 587
33 9 92
33 12 797
33 13 200
33 14 357
33 16 930
33 17 521
33 21 33
33 22 968
33 24 851
33 25 840
33 26 843
33 29 134
33 30 34
33 31 513
33 32 650
33 35 211
34 0 447
34 1 265
34 4 452
34 5 53
34 7 974
34 8 656
34 10 451
34 11 147
34 12 206
34 13 63
34 14 721
34 15 554
34 17 749
34 18 198
34 19 261
34 20 73
34 21 1
34 22 162
34 23 382
34 24 840
34 27 142
34 30 153
34 33 816
35 1 561
35 3 865
35 4 254
35 5 472
35 6 425
35 9 861
35 11 487
35 13 746
35 14 470
35 15 693
35 17 999
35 21 202
35 22 422
35 23 937
35 24 397
35 27 398
35 28 322
35 29 306
35 31 289
35 32 350
22 177
0 21
4 10 70
18 17 88
20 18 408
11 20 592
5 4 977
12 17 918
16 17 123
13 17 129
3 5 965
3 0 315
1 2 881
15 11 147
17 21 233
9 1 24
3 2 535
14 11 754
11 12 622
10 7 623
11 13 368
0 3 816
4 2 763
0 10 398
4 3 287
6 2 870
7 0 964
1 0 681
8 6 325
14 18 905
11 18 185
20 14 297
5 0 998
6 0 715
17 16 460
15 14 38
5 10 596
2 9 83
7 1 482
2 1 323
19 11 794
17 12 266
9 7 412
17 11 931
19 13 380
7 6 313
18 19 522
9 3 751
21 13 726
18 14 903
13 20 19
7 10 702
17 19 703
9 2 276
15 12 597
14 15 2
9 8 919
21 12 506
17 20 258
14 13 51
7 9 571
2 5 957
13 15 816
3 6 189
20 15 957
14 20 823
0 1 443
7 2 382
4 6 225
12 16 805
20 21 556
12 21 230
18 20 875
19 20 647
4 5 945
16 11 76
2 0 433
11 19 658
12 11 634
18 16 842
19 17 908
10 1 120
12 18 246
3 8 487
5 8 919
20 19 707
3 10 244
4 0 874
18 13 812
16 21 706
13 11 746
1 8 834
20 12 224
1 10 904
8 5 310
5 7 798
11 16 138
1 3 241
11 21 220
8 7 222
15 13 370
6 5 400
6 1 744
17 14 394
6 7 90
15 18 79
8 0 171
9 6 950
14 21 311
10 3 922
4 9 995
18 12 725
5 2 545
16 14 958
1 7 253
2 10 684
0 2 16
19 14 786
2 3 899
10 4 997
4 1 272
1 5 978
19 16 897
13 12 698
6 10 29
16 20 815
17 18 133
8 2 723
2 6 696
10 8 685
15 16 510
21 11 802
13 14 825
10 5 297
2 4 803
9 0 784
10 6 162
11 14 129
16 12 479
17 13 925
3 9 862
11 17 108
8 4 208
0 5 838
9 4 668
16 19 902
13 19 325
21 15 690
20 16 75
12 15 759
6 9 630
0 7 458
10 0 704
5 1 164
5 6 136
20 17 451
16 13 483
6 3 576
14 17 717
17 15 136
15 17 368
0 8 466
6 8 252
7 5 58
7 8 692
5 9 759
8 9 219
2 7 185
8 10 913
12 14 304
16 15 843
19 18 485
14 19 388
14 12 34
11 15 778
0 6 800
21 16 601
7 3 473
19 12 578
0 0