QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797729#5145. Shortest PathxyjAC ✓249ms255044kbC++114.2kb2024-12-03 17:15:222024-12-03 17:15:22

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5984kb

input:

4
3 2 10
1 2 5
2 3 4
3 0 1000000000
3 3 100
1 2 3
1 3 4
2 3 5
4 6 1000000000
1 2 244
1 2 325
1 4 927
3 3 248
2 4 834
3 4 285

output:

125
0
15300
840659991

result:

ok 4 number(s): "125 0 15300 840659991"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7984kb

input:

400
4 7 850187899
1 2 83
1 2 24
3 1 23
2 3 80
3 3 65
1 2 55
2 4 31
4 7 297586795
3 4 54
1 1 66
2 2 75
1 3 68
1 4 27
1 4 29
2 3 96
5 7 217277444
3 3 9
3 4 36
2 2 77
5 5 38
3 3 6
1 2 18
1 2 23
5 6 379032278
5 5 96
4 3 92
3 2 49
4 3 44
1 4 19
1 1 18
5 6 534284598
5 1 59
1 2 2
3 3 55
2 2 24
5 4 34
2 4 7...

output:

191476186
406722183
0
0
58483482
115858544
177378789
656019644
858116309
0
38761681
633010531
0
696693112
919354187
122684249
865793975
91541737
248634956
0
374201737
455984810
284991806
322357914
0
514668426
407812429
555256220
0
419773408
989291360
743372489
0
716008724
0
189418326
244106015
41273...

result:

ok 400 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 6128kb

input:

400
4 6 415388949
4 2 6853
4 3 5541
1 2 6273
4 4 8561
4 1 9638
4 2 8341
4 6 195566032
2 3 6344
1 1 7616
3 1 4823
4 1 647
4 4 7091
4 2 6307
4 6 720662513
3 3 4435
2 1 4448
4 3 3142
4 1 6670
2 4 5545
2 3 2990
5 7 806244066
3 2 3989
4 3 8157
5 2 612
3 5 8294
1 1 2114
3 4 2311
5 2 8825
5 6 894954332
4 1...

output:

392283147
970308579
491899881
0
495762954
10156057
664457753
0
575852185
134843393
933754264
590740253
0
490859785
724017823
957609109
0
622353894
279038091
426991125
0
637389724
0
75171267
749597224
258493187
250907837
497917111
886569508
828505392
68793449
224109727
139499076
786372001
894480753
4...

result:

ok 400 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 6000kb

input:

400
4 6 626798206
4 4 835705
3 2 236950
2 4 952235
1 2 581609
3 2 204788
2 1 947505
5 7 121450775
2 2 288007
3 2 130288
5 4 76431
4 5 23594
2 5 675316
4 1 192066
3 3 275296
5 7 867412084
1 4 473530
4 3 242225
2 3 459428
2 2 852747
4 1 242292
1 2 9788
3 2 175026
5 6 270426492
5 4 75346
4 2 880851
5 2...

output:

359593563
746525185
0
0
73714485
664197694
720306834
414192169
852090104
263236207
112963474
326265087
32838160
575302262
917139513
704934710
717038510
608349067
804139086
30761395
0
885174847
903442468
235788993
315187893
267383762
881704492
392427980
511540414
82510129
841018587
628947824
90374582...

result:

ok 400 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 6080kb

input:

400
4 7 237940126
2 3 811465519
3 1 406242509
4 2 568535949
4 4 916500298
3 2 79853489
2 4 485382745
2 3 421622532
5 6 680552144
5 4 315694734
4 1 414031567
5 4 530765372
2 5 734798151
4 5 677388912
3 2 511925895
4 6 174169143
1 2 355579133
1 1 374390087
3 3 393590012
2 3 72192607
1 2 898660531
3 1 ...

output:

80828666
371586866
0
167800461
410107945
445437334
0
610069154
796266829
467729673
259462318
581867042
658714588
354982099
590749802
487914460
0
115063504
426498590
124790015
0
408391987
0
108209715
16338078
814297806
454529244
185281507
453042901
940987029
353015051
435087926
0
0
246967770
0
929531...

result:

ok 400 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 12452kb

input:

40
46 100 796871833
14 45 5
34 15 75
18 35 36
18 24 62
7 36 17
17 9 45
31 33 11
33 15 34
23 5 72
23 27 44
16 15 3
10 28 18
1 36 89
4 40 32
46 43 55
14 22 61
30 15 36
8 2 82
21 12 15
42 45 78
26 40 11
46 32 42
26 46 10
39 40 83
37 39 95
45 27 45
32 37 91
2 19 34
9 7 74
28 5 99
3 44 34
33 38 6
18 13 7...

output:

486700134
857700687
608672173
864577567
889360467
813527860
503310571
949592684
427562681
54612131
295765111
981822742
297387832
510195726
183427910
339067217
163331381
781441071
387001805
800276039
215789954
315236685
325091800
561623521
0
564200504
58828620
705573545
860792488
149660643
968795549
...

result:

ok 40 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 12212kb

input:

40
49 98 637035062
28 11 4294
36 2 7586
44 33 6870
19 3 4054
38 5 2009
2 26 6184
5 45 2951
33 23 7022
18 38 3008
46 19 8137
49 18 6080
18 37 8209
18 8 9077
31 43 6509
42 22 5743
2 18 9127
16 2 8584
38 11 7504
15 12 2867
1 19 8063
11 26 9017
17 3 6127
23 19 5473
13 38 4521
25 37 7360
31 34 6656
47 22...

output:

821693058
71016907
857321273
783587298
982610065
980278015
275485521
971090373
233315886
399922806
0
278608644
378866648
599249221
340396754
540768603
530594607
776205772
730857174
933810552
227365258
382149558
937071245
521975672
690097593
73883754
33862436
462058733
443441774
438932117
64257634
58...

result:

ok 40 numbers

Test #8:

score: 0
Accepted
time: 5ms
memory: 12112kb

input:

40
46 95 723931456
35 20 947776
31 38 238603
37 17 836768
12 40 35931
25 6 38152
17 27 195009
37 26 230999
2 12 963773
22 18 283748
9 34 499029
30 9 601767
38 4 966623
21 3 740901
32 31 66189
9 46 751585
38 27 412857
40 28 136769
2 17 118003
21 18 102142
45 31 319817
33 13 496656
16 5 168278
37 15 9...

output:

862261239
934208524
676535904
425060961
680809878
921710894
166137599
490099382
786664556
667359023
117551032
65363912
805410419
453568705
636903494
876708711
0
874460066
688545496
770335168
196141613
286072255
826782785
385627101
487670842
692193056
921891801
493485960
746027697
94281264
761466453
...

result:

ok 40 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 12380kb

input:

40
50 90 857563025
2 11 393746492
45 46 345072720
13 18 637861512
47 3 571609922
50 35 402605542
23 36 161663167
27 20 267096312
50 47 967313350
6 23 797326121
12 47 19611590
32 22 693454539
6 40 749059549
14 47 655748726
9 32 774397775
49 22 471626653
18 23 775770441
8 47 263012466
17 27 714895319
...

output:

823474705
897491227
830605997
310507990
396608942
755858403
192083730
558837131
397169944
133851804
124398473
334337729
676169091
498313169
10613351
887468199
938570424
730866390
93748497
991959257
969327421
950615046
29589899
290773789
436801411
468797561
311350228
807413343
196500651
737421403
330...

result:

ok 40 numbers

Test #10:

score: 0
Accepted
time: 39ms
memory: 66308kb

input:

4
452 997 787553451
224 333 31
99 434 28
63 105 64
15 304 41
43 356 18
359 280 70
446 415 69
256 296 47
276 108 23
138 249 8
152 281 31
284 122 45
1 10 39
348 216 4
260 386 51
442 340 3
305 316 81
103 267 18
444 14 16
418 221 20
366 343 72
448 265 44
419 417 60
433 251 19
138 373 42
221 251 52
219 2...

output:

920051934
337790394
379237832
857209587

result:

ok 4 number(s): "920051934 337790394 379237832 857209587"

Test #11:

score: 0
Accepted
time: 37ms
memory: 58800kb

input:

4
488 933 522189685
296 341 4432
469 325 7333
230 83 8870
61 45 9898
236 85 6295
90 304 7287
486 400 6268
115 485 7251
455 214 9376
74 402 2519
461 119 4761
379 238 966
235 139 5469
365 82 5901
143 101 4371
110 323 8173
126 186 9270
451 315 9574
340 282 2321
152 360 7030
112 317 3895
388 484 1202
21...

output:

603678306
943491463
173268290
201396620

result:

ok 4 number(s): "603678306 943491463 173268290 201396620"

Test #12:

score: 0
Accepted
time: 26ms
memory: 58284kb

input:

4
475 925 862065786
223 259 326692
311 176 146944
236 82 519523
454 402 81050
314 40 916288
147 431 876771
457 438 621257
400 157 931920
22 170 696985
236 219 335364
229 83 709348
238 112 98295
284 436 112450
38 119 757155
256 275 92474
194 116 661424
306 15 548944
308 426 87714
9 203 246801
288 448...

output:

0
700852946
806811784
955695134

result:

ok 4 number(s): "0 700852946 806811784 955695134"

Test #13:

score: 0
Accepted
time: 37ms
memory: 63800kb

input:

4
468 943 401471037
16 76 84807660
391 15 339856779
217 269 160461855
105 400 445538323
90 401 136863755
23 152 971192392
51 339 208461283
467 55 188586800
61 65 493966321
140 229 716542747
182 270 337275222
154 76 601108616
377 254 684327428
103 375 734134843
327 225 26827769
26 248 368659099
457 5...

output:

158572391
663760343
713171553
450639895

result:

ok 4 number(s): "158572391 663760343 713171553 450639895"

Test #14:

score: 0
Accepted
time: 247ms
memory: 251992kb

input:

1
1967 4772 636170050
1469 497 29
698 1900 25
1731 103 98
1190 812 60
1066 904 32
569 223 41
1263 1625 89
300 483 43
422 734 52
229 88 58
1319 1391 15
1684 71 83
1306 789 98
288 1736 43
269 1183 72
696 707 10
1439 55 18
159 356 11
1901 17 82
1143 1004 14
1792 1663 29
1240 1515 66
548 1911 79
1554 14...

output:

12502270

result:

ok 1 number(s): "12502270"

Test #15:

score: 0
Accepted
time: 215ms
memory: 230632kb

input:

1
1802 4503 646877183
1127 984 7603
556 882 5723
127 507 7174
433 370 2556
39 1516 9375
334 805 1773
341 55 8686
1570 1207 2941
13 306 2050
1080 752 1702
197 663 1476
1137 1426 3546
568 127 7250
1442 171 223
979 48 4046
556 1172 6317
1293 452 3992
1439 296 4087
1783 529 6601
773 1796 3624
198 324 81...

output:

273339035

result:

ok 1 number(s): "273339035"

Test #16:

score: 0
Accepted
time: 240ms
memory: 243200kb

input:

1
1904 4785 968128956
859 417 113491
403 1270 191589
129 1812 622246
1270 1381 15261
879 1580 307339
431 1471 63479
812 1707 636114
1078 1600 402010
125 150 168133
1551 962 517476
1341 82 13938
691 1085 223701
1567 1596 985654
1196 1792 196604
113 1335 773004
948 1566 912289
1811 1804 809238
1344 94...

output:

774302007

result:

ok 1 number(s): "774302007"

Test #17:

score: 0
Accepted
time: 245ms
memory: 244124kb

input:

1
1905 4762 791011485
308 1642 674031390
170 417 451432236
668 1138 975582181
13 559 257035921
225 658 268340515
111 488 381378525
397 2 542379808
395 956 690894704
687 390 942311067
1257 1140 945365111
105 1789 545765059
393 1382 996273411
620 1639 137431157
126 1252 713096043
908 923 621490871
120...

output:

311528206

result:

ok 1 number(s): "311528206"

Test #18:

score: 0
Accepted
time: 0ms
memory: 8116kb

input:

400
4 7 99
1 2 83
1 2 24
3 1 23
2 3 80
3 3 65
1 2 55
2 4 31
4 7 95
3 4 54
1 1 66
2 2 75
1 3 68
1 4 27
1 4 29
2 3 96
5 7 44
3 3 9
3 4 36
2 2 77
5 5 38
3 3 6
1 2 18
1 2 23
5 6 78
5 5 96
4 3 92
3 2 49
4 3 44
1 4 19
1 1 18
5 6 98
5 1 59
1 2 2
3 3 55
2 2 24
5 4 34
2 4 79
4 7 93
3 3 75
3 3 32
3 4 89
1 1 6...

output:

116781
124953
0
0
16283
153948
3360
37746
3214
0
1203
36225
0
12033
34881
20372
72929
20770
32045
0
12688
19286
20491
5280
0
49783
2891
53378
0
19584
1615
38239
0
61082
0
1195
29000
56628
15548
232
0
0
3797
5112
74176
58522
27897
303
50957
99282
4221
0
0
4709
9568
0
0
6125
0
5866
34895
16611
0
1350
...

result:

ok 400 numbers

Test #19:

score: 0
Accepted
time: 6ms
memory: 12604kb

input:

40
46 100 33
14 45 5
34 15 75
18 35 36
18 24 62
7 36 17
17 9 45
31 33 11
33 15 34
23 5 72
23 27 44
16 15 3
10 28 18
1 36 89
4 40 32
46 43 55
14 22 61
30 15 36
8 2 82
21 12 15
42 45 78
26 40 11
46 32 42
26 46 10
39 40 83
37 39 95
45 27 45
32 37 91
2 19 34
9 7 74
28 5 99
3 44 34
33 38 6
18 13 76
22 34...

output:

4762
8002
4442
15470
13266
4968
4462
1299
6912
16213
5136
6642
506
4400
4398
1425
2865
5336
22834
11704
39316
9612
6850
20910
0
1981
7529
867
13612
2966
1558
24729
17851
839
246
10866
5163
0
17745
1958

result:

ok 40 numbers

Test #20:

score: 0
Accepted
time: 41ms
memory: 67796kb

input:

4
452 997 51
224 333 31
99 434 28
63 105 64
15 304 41
43 356 18
359 280 70
446 415 69
256 296 47
276 108 23
138 249 8
152 281 31
284 122 45
1 10 39
348 216 4
260 386 51
442 340 3
305 316 81
103 267 18
444 14 16
418 221 20
366 343 72
448 265 44
419 417 60
433 251 19
138 373 42
221 251 52
219 281 53
1...

output:

7831
7513
34550
19865

result:

ok 4 number(s): "7831 7513 34550 19865"

Test #21:

score: 0
Accepted
time: 30ms
memory: 68192kb

input:

4
490 925 297
467 123 28
222 349 101
433 368 965
33 407 762
133 314 125
65 76 653
347 65 684
397 405 849
360 37 872
212 393 589
474 130 918
27 302 818
375 358 692
238 326 852
430 173 778
187 51 900
458 477 377
444 438 83
401 391 915
396 380 642
38 306 36
212 75 121
140 324 984
133 343 222
102 214 74...

output:

959896
3565624
2525238
2125871

result:

ok 4 number(s): "959896 3565624 2525238 2125871"

Test #22:

score: 0
Accepted
time: 244ms
memory: 252048kb

input:

1
1967 4772 50
1469 497 29
698 1900 25
1731 103 98
1190 812 60
1066 904 32
569 223 41
1263 1625 89
300 483 43
422 734 52
229 88 58
1319 1391 15
1684 71 83
1306 789 98
288 1736 43
269 1183 72
696 707 10
1439 55 18
159 356 11
1901 17 82
1143 1004 14
1792 1663 29
1240 1515 66
548 1911 79
1554 1484 48
1...

output:

11929

result:

ok 1 number(s): "11929"

Test #23:

score: 0
Accepted
time: 249ms
memory: 251124kb

input:

1
1966 4897 563
1811 1801 86
1336 714 22
1515 539 229
1254 1496 304
995 1024 722
1208 1073 13
791 604 520
81 280 271
84 1286 73
900 246 143
1432 506 282
415 1634 167
1039 1199 896
267 1705 285
993 1726 275
1086 287 809
730 967 658
1015 1965 690
1748 386 1
586 1525 101
270 513 367
1470 1701 270
215 1...

output:

1336754

result:

ok 1 number(s): "1336754"

Test #24:

score: 0
Accepted
time: 219ms
memory: 230568kb

input:

1
1802 4503 7183
1127 984 7603
556 882 5723
127 507 7174
433 370 2556
39 1516 9375
334 805 1773
341 55 8686
1570 1207 2941
13 306 2050
1080 752 1702
197 663 1476
1137 1426 3546
568 127 7250
1442 171 223
979 48 4046
556 1172 6317
1293 452 3992
1439 296 4087
1783 529 6601
773 1796 3624
198 324 8193
60...

output:

319606739

result:

ok 1 number(s): "319606739"

Test #25:

score: 0
Accepted
time: 2ms
memory: 5992kb

input:

2000
1 2 647038555
1 1 40
1 1 97
1 1 74645111
1 1 87
1 0 757844690
1 2 128544550
1 1 43
1 1 8
1 0 680136526
1 2 251170622
1 1 84
1 1 53
1 2 975912407
1 1 77
1 1 47
1 1 804037082
1 1 63
1 1 837324676
1 1 75
1 1 569378052
1 1 79
1 0 679808874
1 2 907993686
1 1 56
1 1 79
1 2 597770899
1 1 100
1 1 2
1 2...

output:

641668068
607837668
0
82531903
0
120583479
116626946
839742525
397223292
571308770
0
544205144
50421659
413916310
589897903
0
637797301
578750960
536904737
826137765
204383380
500960112
583326689
120349604
0
438014838
165350730
944103697
252679315
0
0
664386252
606558449
0
0
0
0
367191917
416162255
...

result:

ok 2000 numbers

Test #26:

score: 0
Accepted
time: 0ms
memory: 6012kb

input:

1000
2 3 909836337
1 2 90
1 1 32
2 1 59
2 2 362406774
2 2 42
2 1 56
2 3 379536907
2 2 41
1 1 95
1 1 36
1 2 735142770
1 1 53
1 1 39
1 2 533175889
1 1 96
1 1 10
1 2 669548481
1 1 17
1 1 74
2 1 359015993
1 2 93
1 3 240662052
1 1 3
1 1 3
1 1 14
2 0 301896813
2 1 72404989
1 2 22
2 0 229816421
1 0 2638643...

output:

569510492
813869988
0
230459400
724945610
528694974
492655617
455157597
0
919954058
0
0
0
0
771562059
875037930
543441658
0
0
0
928499692
932208271
276011901
0
393988553
0
0
11328921
527875549
513162226
32244946
0
315372527
659688615
0
0
147186241
258643362
222896861
941223347
646745047
246738503
57...

result:

ok 1000 numbers

Test #27:

score: 0
Accepted
time: 1ms
memory: 5996kb

input:

400
1 4 64191875
1 1 46
1 1 152
1 1 695
1 1 264
1 3 251383800
1 1 90
1 1 844
1 1 803
3 7 103698207
1 2 2
1 3 738
1 1 775
2 3 35
2 3 40
3 2 127
3 1 945
5 2 576238230
3 1 300
4 1 750
4 2 9853674
1 4 832
1 1 799
2 5 427531056
2 1 268
2 1 468
1 1 289
2 1 126
2 2 169
4 1 54647875
4 1 835
4 6 61070475
4 2...

output:

90767770
968788351
414182689
0
622178818
550567855
861220952
194113614
639473589
564465883
0
0
0
349324325
169064054
684615719
0
418591517
0
483448670
101663583
228633032
0
818885262
0
904525563
0
0
0
789294703
448132091
0
229247055
243539501
941573482
625422494
0
0
435003489
868104925
937823553
387...

result:

ok 400 numbers

Test #28:

score: 0
Accepted
time: 3ms
memory: 12192kb

input:

40
38 78 865475435
18 4 609
25 4 933
12 1 906
11 18 635
7 5 20
25 36 40
2 19 267
9 24 879
27 1 423
19 28 493
15 29 273
29 4 431
19 30 625
28 19 150
12 28 6
29 11 591
13 6 719
21 23 679
31 5 56
8 30 862
18 15 959
14 4 697
27 29 97
35 4 422
8 30 247
33 32 594
12 1 886
32 25 190
10 36 382
30 32 506
26 ...

output:

629897538
0
578441871
352762908
0
119907192
252529872
418986528
423687001
79462756
0
338198962
841293993
723619799
724684783
283764715
5162008
361237609
944483006
248134199
154734107
196125020
974806068
0
189200138
845477688
269036857
16680022
377661052
126692697
639362001
379759184
392254611
658369...

result:

ok 40 numbers

Test #29:

score: 0
Accepted
time: 10ms
memory: 84152kb

input:

2
575 0 836060593
617 1 64177603
132 184 69

output:

0
0

result:

ok 2 number(s): "0 0"

Test #30:

score: 0
Accepted
time: 59ms
memory: 254952kb

input:

1
2000 2000 2000
1 2 355880635
2 3 456522298
3 4 324565104
4 5 747445986
5 6 679248225
6 7 4352646
7 8 208956893
8 9 45994494
9 10 951727147
10 11 346142259
11 12 728408730
12 13 119918687
13 14 92886231
14 15 202971510
15 16 199363198
16 17 54815971
17 18 895630578
18 19 721401463
19 20 794946673
2...

output:

603068227

result:

ok 1 number(s): "603068227"

Test #31:

score: 0
Accepted
time: 68ms
memory: 254856kb

input:

1
2000 2000 4000
1 2 182921902
2 3 48872927
3 4 167822145
4 5 46642771
5 6 489188914
6 7 683374972
7 8 718444172
8 9 103284880
9 10 744876872
10 11 170580073
11 12 490141955
12 13 669350485
13 14 269841137
14 15 481236009
15 16 140665617
16 17 725024668
17 18 338302370
18 19 334372561
19 20 37879445...

output:

622631984

result:

ok 1 number(s): "622631984"

Test #32:

score: 0
Accepted
time: 81ms
memory: 255028kb

input:

1
2000 2000 10000
1 2 461190862
2 3 425336199
3 4 468667193
4 5 294585606
5 6 756031284
6 7 783289178
7 8 692784037
8 9 83162198
9 10 381551025
10 11 353987043
11 12 902107063
12 13 75901968
13 14 975664511
14 15 512540269
15 16 990551987
16 17 994957464
17 18 313146509
18 19 250762776
19 20 5555707...

output:

349410253

result:

ok 1 number(s): "349410253"

Test #33:

score: 0
Accepted
time: 66ms
memory: 254960kb

input:

1
2000 2000 1000000000
1 2 553915152
2 3 902510038
3 4 101858085
4 5 190345717
5 6 324590535
6 7 626504126
7 8 37976263
8 9 519704003
9 10 113923785
10 11 903085815
11 12 294696558
12 13 842676848
13 14 199244213
14 15 649479023
15 16 555649438
16 17 832161693
17 18 911579664
18 19 180430231
19 20 8...

output:

455248531

result:

ok 1 number(s): "455248531"

Test #34:

score: 0
Accepted
time: 59ms
memory: 255020kb

input:

1
2000 2000 10000
1 2 461190862
2 3 425336199
3 4 468667193
4 5 294585606
5 6 756031284
6 7 783289178
7 8 692784037
8 9 83162198
9 10 381551025
10 11 353987043
11 12 902107063
12 13 75901968
13 14 975664511
14 15 512540269
15 16 990551987
16 17 994957464
17 18 313146509
18 19 250762776
19 20 5555707...

output:

26790582

result:

ok 1 number(s): "26790582"

Test #35:

score: 0
Accepted
time: 60ms
memory: 255024kb

input:

1
2000 2000 1000000000
1 2 820150092
2 3 420364105
3 4 176506884
4 5 700582388
5 6 315450982
6 7 770441035
7 8 216500322
8 9 774099762
9 10 183930736
10 11 117606849
11 12 355271417
12 13 255200840
13 14 897186549
14 15 7298706
15 16 318296788
16 17 744488046
17 18 261280417
18 19 234842474
19 20 40...

output:

623557504

result:

ok 1 number(s): "623557504"

Test #36:

score: 0
Accepted
time: 66ms
memory: 254840kb

input:

1
2000 2000 1000000000
1 2 998233516
2 3 848688757
3 4 770287437
4 5 726211865
5 6 294800235
6 7 460144003
7 8 91496497
8 9 822316454
9 10 404864892
10 11 694878327
11 12 29531856
12 13 16760583
13 14 834986639
14 15 32125140
15 16 685491303
16 17 967160155
17 18 394785036
18 19 389090033
19 20 9815...

output:

814619453

result:

ok 1 number(s): "814619453"

Test #37:

score: 0
Accepted
time: 64ms
memory: 254980kb

input:

1
2000 2000 1000000000
1 2 881349644
2 3 717204898
3 4 509292183
4 5 456874047
5 6 274149489
6 7 4622780
7 8 821268480
8 9 165500442
9 10 330831751
10 11 977182509
11 12 408825000
12 13 73287623
13 14 772786729
14 15 206694677
15 16 202428922
16 17 44608072
17 18 678032758
18 19 393594487
19 20 1499...

output:

355692462

result:

ok 1 number(s): "355692462"

Test #38:

score: 0
Accepted
time: 83ms
memory: 254908kb

input:

1
2000 1999 1000000000
1 2000 1000000000
2 3 10000
1 2 10001
4 5 9998
1 4 30280
6 7 9997
1 6 41001
8 9 9994
1 8 75806
10 11 9991
1 10 112123
12 13 9988
1 12 149951
14 15 9985
1 14 189960
16 17 9982
1 16 232271
18 19 9980
1 18 261222
20 21 9978
1 20 290387
22 23 9973
1 22 366658
24 25 9972
1 24 38275...

output:

220124626

result:

ok 1 number(s): "220124626"

Test #39:

score: 0
Accepted
time: 76ms
memory: 254964kb

input:

1
2000 1999 1000000000
1 2000 1000000000
2 3 10000
1 2 10001
4 5 9999
1 4 20863
6 7 9996
1 6 54188
8 9 9991
1 8 114056
10 11 9989
1 10 139378
12 13 9987
1 12 165892
14 15 9983
1 14 221493
16 17 9981
1 16 250862
18 19 9980
1 18 265690
20 21 9975
1 20 344665
22 23 9974
1 22 361001
24 25 9969
1 24 4430...

output:

191977428

result:

ok 1 number(s): "191977428"

Test #40:

score: 0
Accepted
time: 120ms
memory: 255044kb

input:

1
2000 2998 1000000000
1 2000 1000000000
2 3 10000
1 2 10001
2 2 1000000000
4 5 9998
1 4 30280
4 4 1000000000
6 7 9997
1 6 41001
6 6 1000000000
8 9 9994
1 8 75806
8 8 1000000000
10 11 9991
1 10 112123
10 10 1000000000
12 13 9988
1 12 149951
12 12 1000000000
14 15 9985
1 14 189960
14 14 1000000000
16...

output:

794773407

result:

ok 1 number(s): "794773407"

Test #41:

score: 0
Accepted
time: 131ms
memory: 254596kb

input:

1
2000 2998 1000000000
1 2000 1000000000
2 3 10000
1 2 10001
2 2 1000000000
4 5 9999
1 4 20863
4 4 1000000000
6 7 9996
1 6 54188
6 6 1000000000
8 9 9991
1 8 114056
8 8 1000000000
10 11 9989
1 10 139378
10 10 1000000000
12 13 9987
1 12 165892
12 12 1000000000
14 15 9983
1 14 221493
14 14 1000000000
1...

output:

738479011

result:

ok 1 number(s): "738479011"