陈奕朴
(智灵提高小班（乘以五）)
1
#include <bits/stdc++.h>
#define ll long long
#define inf 1e9
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
int n,m,mi[N],ma[N],pre[N],vis[N],ans[N],cnt,dis[N];
vector<pii>g[N];
void bfs(){
queue<int>q;
dis[1]=0;
vis[1]=1;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto x:g[u]){
int v=x.first,w=x.second;
int aaa=dis[u]+1;
if(aaa>dis[v]){
continue;
}
if(aaa<dis[v]){
dis[v]=aaa;
ma[v]=max(w,ma[u]);
mi[v]=min(w,mi[u]);
pre[v]=u;
}
else if(max(w,ma[u])-min(w,mi[u])>=ma[v]-mi[v]){
ma[v]=max(w,ma[u]);
mi[v]=min(w,mi[u]);
pre[v]=u;
}
if(vis[v]){
continue;
}
q.push(v);
vis[v]=1;
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
memset(dis,0x3f,sizeof dis);
int u,v,w;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for(int i=1;i<=n;i++){
ma[i]=-inf;
mi[i]=inf;
}
bfs();
cout<<dis[n]<<"\n";
for(int i=n;i!=0;i=pre[i]){
ans[++cnt]=i;
}
for(int i=cnt;i>=1;i--){
cout<<ans[i]<<' ';
}
return 0;
}
陈奕朴
(智灵提高小班（乘以五）)
3
9
1 157 863 68 484 899 754 111 816 1000
陈奕朴
(智灵提高小班（乘以五）)
6
1000 2000
1 624 468751243
1 478 83273719
1 967 119316718
1 828 967545249
1 679 953902918
1 738 107743839
1 53 854838269
1 765 279991778
1 731 453125581
1 662 730888915
1 157 50599211
1 27 721908318
1 962 343041365
1 728 213265001
1 584 767091453
1 342 367934835
1 266 330713598
1 150 252319727
1 836 69935866
1 636 788053605
1 321 129878198
1 127 330525548
1 11 952060575
1 712 408935686
1 254 287215026
1 435 354502953
1 318 776071222
1 701 118991512
1 642 207820841
1 613 62976537
1 763 344473602
1 551 656536219
1 387 716321966
1 908 322767654
1 152 166033983
1 866 204303794
1 500 196170443
1 700 294168680
1 117 118062197
1 719 93925067
1 87 188902656
1 915 179610681
1 535 246775716
1 761 869857535
1 344 471086152
1 726 945238388
1 444 354742478
1 686 335637266
1 531 962876384
1 634 153168128
1 748 50201263
1 123 281731677
1 330 468124494
1 487 671668614
1 895 49820099
1 70 177862290
1 437 393648879
1 894 23682695
1 91 899436325
1 19 722703812
1 530 615605158
1 511 72637773
1 184 927045004
1 856 702867845
1 351 132218347
1 149 250347752
1 380 764201257
1 206 477071758
1 995 95190128
1 48 381141425
1 795 544780398
1 433 701702233
1 126 49501559
1 284 833962768
1 603 412078741
1 395 623560784
1 977 564029652
1 544 251393956
1 717 339849525
1 295 648034818
1 282 707081201
1 588 36439648
1 474 749849199
1 508 335511707
1 455 363070902
1 743 186760279
1 301 419697195
624 639 281286326
700 914 293953935
301 888 818500097
200 395 566438530
463 962 142390446
588 687 895003350
11 527 756863978
731 905 894554565
700 942 262771703
456 717 735013806
487 564 499994602
75 544 672245115
346 584 516934700
612 701 497831146
117 300 548809240
284 513 397359919
238 743 971859727
262 387 844008431
523 856 885895343
428 551 856746921
189 761 58698766
855 977 760364625
765 801 539793221
48 950 399864261
145 395 714290945
206 468 381713552
164 719 65697672
508 881 872814518
478 788 518332131
761 954 155240492
288 433 836676142
597 738 767859686
127 465 981700854
603 675 820880266
208 915 784207161
152 158 847346476
344 803 501208868
668 856 609288627
743 963 371452073
613 886 435051537
287 321 936647216
70 432 578465536
117 480 198129165
532 795 588157542
435 610 299686416
117 460 936082058
561 908 123743491
157 583 235403212
555 679 833969935
739 908 746261392
11 57 798817466
731 994 773782942
79 184 114010764
70 569 625502176
157 863 388608128
64 603 714670373
478 826 577941781
487 732 66311389
230 967 118407939
102 478 455312249
544 804 586568702
616 662 858782812
301 399 483245916
700 887 994299405
634 812 567997403
530 628 689718754
568 584 520511294
123 983 2394052
331 738 468314409
444 922 167879381
526 544 433432881
490 726 254848469
452 712 421342523
374 726 991749857
254 512 715125397
36 908 839741876
213 508 978897319
269 712 78337337
433 878 369804482
798 995 301803069
415 738 75969702
150 776 69897051
36 294 11891697
57 169 606001202
526 840 936108013
481 922 667689146
29 812 318373065
504 855 317214583
200 439 886420172
513 601 694900340
798 823 9816761
695 994 177646519
582 732 181660310
532 984 418539252
219 230 784383413
591 739 566342974
71 523 595764368
13 675 145106390
750 855 695066966
235 983 708095170
454 583 149547935
528 963 634004718
458 922 446925205
331 529 75082482
463 633 658831729
616 685 311349337
797 886 5487580
214 490 125083353
228 555 827497106
81 561 103249651
138 452 852918513
687 966 304306954
399 576 97281069
201 415 623185172
163 983 868743365
120 905 358829098
523 783 629264359
333 887 953931668
60 616 518114931
337 886 724884245
468 604 663042067
208 867 414237658
465 476 296582715
480 733 653338285
281 569 636014091
255 527 538569888
583 926 439918113
533 668 781913326
905 919 666255405
569 673 477177816
134 331 296461500
713 732 889442703
610 852 479312294
855 972 4440357
421 732 405540679
68 863 1993017
256 432 68240033
374 813 295814222
75 398 192522038
803 934 766268668
464 922 702877956
618 687 442552574
431 826 543181936
36 598 290024918
621 888 791508173
213 671 582999671
527 627 303575479
359 460 593523715
527 589 473299894
278 612 857925856
103 881 270340914
28 75 350799855
490 735 978770231
408 460 237050454
541 675 348493695
612 658 508899933
776 900 584435299
230 289 315972853
51 468 530816738
207 523 275298946
307 863 102337387
558 914 942921617
518 863 185572747
168 213 459267319
36 720 952260046
40 415 523540600
240 675 5839780
75 229 300164829
881 943 664544997
902 914 890892193
542 886 382687665
451 739 793796794
903 950 514910742
526 969 465717333
158 453 87775894
370 480 492037188
140 513 918026397
472 863 411588434
189 830 592361093
58 399 53055997
315 512 830992427
79 715 813528749
106 262 210483347
788 891 449619925
64 851 726539565
826 944 36998904
317 456 947255882
320 963 460353176
163 389 695476391
494 713 977215371
294 664 451495180
159 830 19045590
106 725 544254970
58 109 855714434
77 713 257360970
542 655 955696396
217 934 691085164
81 882 463184570
112 591 724130007
175 370 272029887
416 658 472496878
54 278 88361059
498 518 600580680
47 934 146366872
713 853 825238175
56 851 465370453
134 506 786356227
381 966 773745327
103 617 911653390
214 313 9706288
591 690 392156238
31 103 491970311
303 673 722925846
163 921 155978195
525 720 659100225
446 598 26909168
51 978 227042868
169 227 316163598
186 458 974004831
29 418 472875754
105 750 974223715
354 919 637506345
292 398 837118386
13 911 212318824
24 408 504775795
167 783 617412924
71 646 894855461
286 797 371794691
133 481 852920696
235 721 977070073
591 755 926430140
829 944 110711975
294 496 41329279
136 307 317467131
58 232 808058122
228 419 358430169
408 663 922468616
255 774 131803047
13 30 37635248
458 654 166776779
228 736 57738511
22 966 718772121
29 937 185469417
106 782 66879923
341 481 902092995
598 874 501566780
270 972 949560929
156 830 621355217
138 657 979120367
722 944 34840408
163 566 892322994
177 618 312915816
359 501 681128654
40 174 127992861
3 528 14299721
68 630 608644341
694 823 953752348
469 926 11250001
26 576 599707189
279 591 358189029
193 289 728363930
138 727 123416464
744 972 856521394
352 431 678635918
484 633 973849556
558 859 751919333
89 289 564062323
823 956 639141732
682 903 117865569
431 992 948475765
421 659 545728729
92 472 439296415
438 852 837820457
439 520 91262039
13 368 234700183
823 982 216762499
541 952 418079387
255 515 140967742
311 733 896613081
235 502 702983353
750 818 570917240
52 783 741784635
454 974 991693222
214 609 228983918
255 932 74528267
114 943 726103652
163 264 331156542
234 944 656667162
695 981 212346399
289 928 970516630
28 82 870452789
252 496 500742774
501 990 970623684
265 525 495221461
292 899 573375143
245 279 841128760
609 825 735089146
233 617 227577366
112 144 248912343
10 630 775972568
341 672 364404550
227 824 745033704
82 635 99438698
368 796 717674201
443 932 510332696
817 952 927548936
755 987 733121831
352 503 1037135
484 873 36067783
419 939 827081330
242 952 845777343
693 992 143855660
392 974 869582181
167 275 110603446
341 986 32254742
7 736 690893095
916 937 95452281
546 727 2132232
128 446 880661300
656 736 369770551
89 298 969483785
96 744 386981044
325 654 871282402
844 952 388357070
566 766 763379170
129 829 235028971
516 978 527784421
114 122 970867317
580 722 812679240
725 970 858632438
590 655 639595951
22 116 706827031
457 911 172527629
609 923 920627614
38 774 430640364
187 484 243017288
232 272 789357672
694 706 387934201
585 882 332415428
112 211 772595140
292 536 538873204
136 917 247428552
133 539 768829447
560 630 397256634
707 782 992912707
232 540 272036810
234 705 492241080
381 573 772119133
82 336 873543901
159 348 822571413
54 507 277410628
94 664 808994243
787 978 449044277
109 651 690529989
31 814 850515892
587 630 574345770
352 429 609592047
41 725 372388692
67 303 655227903
3 819 444594796
338 818 766305814
418 883 941347100
800 978 187976503
837 921 377955468
484 749 405106912
496 626 277604715
821 853 159887215
774 808 737243009
736 940 917528425
89 121 299682338
630 746 86806846
232 521 233744389
381 980 135034681
24 305 384548391
175 322 974220228
363 469 358111601
875 981 998608562
232 845 30477066
202 690 821488166
156 386 943687592
347 438 89909597
647 746 936496330
429 471 793901562
947 970 196993192
10 740 536629864
443 754 109767619
514 970 146035515
825 892 859366043
543 580 958769947
46 144 586702835
545 590 685207921
745 825 842998818
41 314 883629627
345 545 242529023
545 833 143542415
514 702 933156447
34 892 274575627
543 790 122395526
143 892 212505668
606 740 398638826
514 596 597779913
605 754 370110438
574 745 136159615
46 976 259107604
148 471 188905709
353 545 844557151
471 768 368603639
403 471 793345778
393 947 445602092
810 947 222027092
594 754 61282953
299 647 808264407
367 514 912757400
17 647 874588299
198 745 148239083
880 947 988353684
21 46 353538474
892 971 777752514
406 947 665256038
410 740 797773634
314 806 531428621
401 471 396804352
32 754 428944552
46 349 713216675
151 745 365175234
267 892 785624596
314 473 209967067
46 538 461886067
545 678 553496931
650 754 646578610
471 757 813268622
314 595 632063616
402 543 747848133
892 996 6576990
754 929 392726549
46 669 334035027
46 600 418865065
4 647 162717264
545 879 830577601
16 46 32419447
46 190 521587358
130 647 226986345
791 947 787807904
534 892 825417837
517 543 800735363
745 827 161819591
423 740 263404374
745 999 255836019
191 947 475587491
426 471 797119696
466 545 187894134
754 935 282304984
641 892 851128373
567 745 39829534
314 951 763258443
407 754 806152924
15 892 386914125
314 417 615816277
314 640 176371959
373 545 749222036
647 930 19023436
43 314 763429642
314 872 455700675
179 892 680381600
46 936 162127617
514 519 914057836
343 754 197448153
46 665 605771419
482 892 206075899
314 488 434598643
647 945 513866230
545 637 769653114
46 858 962778258
35 471 301529964
754 896 254772674
176 647 143906345
74 545 543558557
324 947 52607966
740 964 538155806
46 131 609033360
197 314 343702566
365 740 331272418
46 304 851022613
283 471 776326251
461 545 236179004
20 545 532496297
216 892 55669413
192 471 343356068
471 577 490136000
745 846 722780083
61 545 98553503
9 892 20328349
471 850 622908647
241 754 400522992
740 807 620450562
545 629 376817046
253 892 164111830
302 514 3917907
754 854 95988397
543 864 161036509
95 892 854737951
258 545 681031591
543 557 300285171
545 696 530005336
259 947 778794578
647 760 995000939
436 947 351362638
108 314 935012275
110 647 301509210
314 602 266524236
86 892 561320321
740 953 274044436
46 699 526597605
740 869 211611307
870 947 929048833
514 988 377166755
251 754 337134530
471 524 599235136
543 550 399322954
543 913 566649644
203 647 287664789
180 471 219426741
59 543 286830103
66 647 94106358
475 647 54058853
55 471 918536761
505 947 184943888
647 793 328805301
46 390 976065586
314 571 645515953
314 565 322338509
545 632 376047724
471 759 375069784
209 545 394237873
188 545 460469578
46 486 855539044
647 753 736499801
799 947 686902447
514 674 832673350
97 892 767505549
46 239 254985607
647 822 681524782
46 76 206947619
471 752 329790641
46 173 224177600
170 647 171860185
385 892 928170344
46 683 477452096
243 514 684482943
357 514 841520573
688 740 922722175
274 314 96188356
172 647 162160966
249 314 464972646
834 892 735325300
740 898 312705818
543 623 739966337
698 754 689206239
383 471 565032699
578 947 656016104
335 545 362746474
562 947 948945380
545 838 883163838
312 471 775797851
815 947 726082828
411 514 265239465
308 947 104774301
442 947 154131306
314 767 841162875
327 754 549890217
514 537 750835336
46 50 624313864
575 745 639233310
543 592 149640931
740 809 434598088
391 754 318164210
543 884 61307757
236 545 917799453
199 543 971843207
46 379 77582490
314 619 293597377
224 314 540981905
215 314 63895236
46 653 432199684
46 210 761930905
471 771 453182034
78 314 551543184
23 545 552398500
741 892 328381590
153 543 130136069
135 740 317476501
44 754 214546956
46 339 357297976
448 740 968790853
647 778 35338310
647 835 816833298
8 947 105718975
413 543 975224720
181 754 707836997
666 947 721112761
314 708 555958816
493 740 99212729
371 754 533496248
447 545 212448952
220 514 808170010
364 514 837218735
579 647 68303103
514 652 769062167
492 543 3723005
111 754 934302191
194 514 827770553
100 514 278963228
72 745 876380283
139 740 122630887
514 832 382307372
183 754 948537186
350 514 288769552
514 927 568243590
46 975 865069679
46 247 656333184
724 740 480395812
740 843 585818196
195 514 955477795
276 514 653863129
745 965 551321834
46 868 285949314
397 647 254594093
62 471 258586217
779 947 795492753
119 543 154387595
740 861 164775477
514 711 399688543
647 716 713718397
548 754 639628338
205 543 60795523
543 841 392182977
485 892 949579953
85 754 240936317
46 773 85621789
314 689 506893032
594 979 594431275
80 951 298745225
410 638 959782346
62 65 379064807
924 929 192402523
216 785 669786631
718 822 420994835
375 534 385738046
155 192 529101889
132 203 204809401
326 492 243564429
489 870 603650726
714 835 350166652
519 998 439073539
310 350 327057282
188 196 923386836
42 170 902347498
509 760 504539484
414 473 70651987
407 849 251076230
16 147 10024781
614 832 476320855
12 834 564514885
93 806 241173522
436 547 410770121
88 151 9951934
21 901 496773116
575 920 783964536
608 861 525831269
602 772 73589406
495 632 611984886
243 958 437370476
742 809 392268114
179 358 976173353
674 764 366284814
176 645 151309791
475 747 628518436
78 948 972804313
316 517 307869984
424 846 952958912
425 884 561159833
477 640 407068483
839 951 475782150
110 907 650671716
178 674 305756820
209 372 10670038
595 729 216449333
394 879 187332936
483 822 475398093
90 461 329311421
85 440 58857036
191 973 463646627
203 422 501786669
411 959 698181410
343 356 874212757
179 182 879827479
396 485 665293683
44 462 474779047
72 99 57019609
362 605 654989924
268 367 376717901
730 945 826101898
146 475 796979079
405 413 428369473
166 752 662591297
756 809 565365920
137 632 662146893
397 697 175511449
385 388 583367822
2 55 333873176
179 769 766288267
909 965 522464282
59 794 981542450
248 253 915310257
139 319 830489888
45 666 341111265
111 876 158273181
130 226 592305432
400 602 544869958
283 643 619394957
154 975 712061759
280 896 379359107
752 918 89578761
734 768 306142392
898 925 529397851
592 680 866996211
586 810 45642275
160 641 46335329
556 606 939498596
35 377 878835997
670 930 887701725
86 376 569252559
222 550 385429939
677 929 475508953
572 833 339444444
198 552 281555506
499 534 838154373
236 737 95238506
702 847 634693916
592 758 51892252
669 777 881283905
209 842 335307108
261 299 245079432
574 599 764788310
49 574 231889085
151 780 367003558
323 854 85369525
125 371 993658778
411 889 64709536
404 861 229903912
260 999 603976069
83 632 123836155
258 450 879264719
550 961 807948506
204 575 363702256
171 864 487260891
285 835 154814302
161 575 815415660
565 649 926627448
340 699 92451654
55 615 808343558
181 361 871250425
73 324 81033586
39 172 250125020
101 436 921947751
118 413 67754132
241 993 454098726
442 946 212191379
332 505 166205817
115 143 85192674
549 834 760595839
14 20 442937761
179 792 444171037
95 141 515760387
153 309 200887824
231 822 49507670
162 524 120524229
302 409 811319311
297 397 666632021
85 912 430342607
492 631 181601302
221 241 359007393
784 868 119925266
420 485 958255770
4 522 711828233
16 805 461669560
751 988 859795577
593 858 467799840
491 505 588646530
191 871 264609685
274 811 497759565
63 838 669130008
44 369 766756418
623 661 150306341
17 906 163570954
393 692 147837802
578 667 96087639
267 931 49121630
442 676 815936941
537 709 473026506
296 579 208959307
357 985 205216076
412 534 697449388
373 434 981367174
534 968 276436508
225 666 784380427
385 910 241000777
644 650 903919453
62 244 868217474
139 329 263254289
306 835 620548360
704 953 78268315
938 965 179027852
218 870 65777555
17 789 922583505
253 625 509005150
239 382 713536323
34 223 65411632
554 988 739239766
384 492 239190083
6 95 332436156
72 142 637841172
165 188 927021094
173 553 161912147
124 436 808736212
708 941 275001531
185 806 288950278
596 862 601298522
605 997 71870484
143 775 90020850
293 810 617206529
35 781 72393488
449 806 812042643
328 548 48710514
353 622 933501037
802 861 827473465
466 786 752890674
224 957 546507809
113 702 379833251
822 848 429272697
277 519 173917356
111 290 685245261
334 929 49987070
559 577 520684695
391 470 927848968
8 897 178726037
563 669 937302452
816 846 612375279
366 711 128875141
271 403 976717361
250 267 935994728
276 991 130073968
194 865 979871856
21 479 600835385
37 371 700488805
605 691 21533184
442 510 427224109
69 913 693981525
197 762 785918228
385 648 419683370
86 427 870699646
246 537 377350384
581 669 613596354
350 877 994174352
173 723 707415759
84 858 765636577
107 771 516002188
702 955 585888815
5 666 710061755
78 703 174302376
475 570 383072404
104 505 160605679
430 869 389363236
611 832 305577657
188 857 480813267
637 989 400426674
283 360 346446598
4 355 634490448
59 497 272952807
619 660 256929583
259 607 618031722
25 209 418074530
445 936 790267878
623 885 226607412
55 933 420398121
349 831 283251549
620 790 63371858
619 820 543521190
710 793 739692823
33 253 10053176
467 896 167013548
98 557 36918373
299 684 369349221
59 904 214586353
263 567 724767490
770 898 577691169
257 827 829434547
216 459 937681314
20 237 59596899
43 860 934862909
18 753 293762226
417 890 517808101
485 960 200688746
212 791 254424867
665 949 750629914
110 291 588953907
312 893 740302250
441 936 951423935
378 964 330506233
273 364 107691213
165 1000 528009140
663 685 684148497
116 754 103761764
143 696 835672084
308 754 664465179
201 240 528517201
207 381 110689531
41 657 195039456
476 694 32696779
626 986 419330484
764 816 98781345
629 724 839976719
60 278 761386268
228 398 190255210
141 1000 403483775
844 939 748031904
330 508 826345773
193 419 355901728
281 994 49856896
162 388 603084796
240 774 911041247
545 647 167451945
527 804 274037449
201 720 536729213
103 633 252260717
338 514 283301071
647 841 399701582
397 517 743644725
543 745 426046278
250 857 481315119
535 700 146443997
122 754 48461834
71 750 644048150
100 677 642891349
122 892 442717714
527 922 917971911
28 646 952470450
303 902 242677972
693 980 215377273
514 745 436971243
72 349 880387213
545 672 924627992
890 941 583111227
602 647 609255669
615 698 658309693
646 658 721741235
514 754 293048857
189 200 700464900
295 803 875215475
514 543 412692708
818 937 279537850
339 947 43037525
46 996 59248518
50 188 355963487
282 564 722924178
47 715 381386947
502 844 721364208
288 535 150468264
31 774 51598331
693 825 125255985
220 723 172066470
31 144 270987383
545 814 76886558
208 474 96191433
254 603 714904539
46 471 157408732
25 98 964352065
129 443 362747519
39 1000 235288952
288 431 593092049
262 399 944078146
393 571 130897883
79 256 544038864
441 794 389558113
16 391 408876013
40 71 810856611
332 991 776925064
430 524 843505864
668 950 636783973
457 782 98444249
526 891 39447680
701 719 21308189
169 604 698524101
689 745 199209167
460 612 106330528
51 333 624539440
42 1000 268702144
307 528 416801558
129 746 791622191
327 762 448935988
陈奕朴
(智灵提高小班（乘以五）)
7
496 520 487222768
811 880 654812287
41 520 618970868
56 159 317664858
66 567 534107072
469 617 640681478
7 187 240375082
498 682 249491012
358 784 469899577
102 855 629938378
52 825 516796976
626 892 206287402
46 111 905382456
126 145 678154267
3 232 396809119
253 753 50765643
206 321 100141732
551 584 604021823
789 1000 381678019
266 616 820342917
336 796 224482268
559 1000 69568160
662 878 385699074
155 1000 283387309
75 634 589410614
575 959 188346151
749 892 910739389
615 945 562467042
264 899 128231060
120 733 437533404
344 624 815588065
152 535 48966997
451 972 651263169
82 516 144215830
621 735 170878585
36 856 931082520
10 539 237796842
136 589 725556895
471 545 437188902
451 928 812449856
633 928 256297105
545 844 568716328
278 564 106674196
347 656 631579811
749 800 499126232
565 906 245281846
307 867 265180283
77 337 151175139
92 721 836149807
68 523 946077988
314 672 393216418
624 634 966372170
871 1000 84197569
210 223 332187866
314 543 610024443
234 782 398838333
292 515 569104871
657 969 323632562
303 956 251862030
27 126 205137807
464 502 625478888
543 773 729648346
46 514 969366202
46 543 313390630
5 958 231612778
227 429 563577017
277 931 556245347
539 916 872918991
367 745 351807045
402 868 265194591
314 745 922632488
28 79 137582144
321 468 396717569
54 386 291018898
96 892 928655019
82 116 282226260
313 695 809476151
26 891 694865149
168 311 15908497
891 984 533583465
31 672 578523136
359 932 777313146
201 456 531649920
347 766 455291548
46 947 426264662
360 860 966543864
294 628 502970224
472 589 757152371
206 415 554481196
959 1000 267653534
796 844 578269027
20 880 502757040
84 402 936164288
498 952 756757824
279 386 803743946
429 981 329324648
501 502 90323513
714 1000 387558346
262 634 819431849
91 435 68002950
368 496 405772205
103 944 448124949
551 613 920484507
79 601 500919312
131 545 806631074
492 833 754127607
635 727 846154858
28 639 70511298
421 633 968522232
561 728 52850733
717 942 707452335
435 836 876247266
336 429 113602594
240 888 127044316
553 1000 194300375
47 77 650648888
452 673 725175470
110 947 110636592
203 210 811913990
140 671 847184654
504 867 132902724
501 940 228279954
484 503 101892683
126 523 599953293
462 709 285814926
316 889 573503560
431 601 694132968
878 887 600125854
57 238 165078276
331 531 459756547
22 169 98536527
150 895 762225076
823 863 208596651
816 1000 440930437
307 735 754637805
546 656 263995169
66 545 92230250
46 314 453382704
625 936 127823833
496 671 69457901
476 984 149710800
514 947 335689893
226 737 711438243
765 994 432148660
103 852 847609921
471 590 972159935
353 514 726454223
421 616 656438755
158 679 106359430
463 943 524209478
81 255 941616675
99 1000 12856918
315 472 987267067
269 750 462358738
76 355 674687456
42 871 731377285
468 886 502356573
298 515 357382294
302 557 676507628
314 754 173321033
865 1000 425191488
109 974 535353835
54 580 6477072
187 521 594236256
432 804 420607315
94 314 442532202
2 876 815902847
97 130 949397564
584 765 94415847
633 950 374232657
230 569 641476653
320 453 767904602
718 909 489040995
754 940 858853505
456 616 14048838
233 647 226842540
211 325 874212754
523 803 95099846
657 928 61651787
415 616 227266499
13 463 98975893
604 732 914529202
219 974 906556628
169 720 198940916
343 843 892321591
311 727 239459296
514 815 294188758
17 565 930881241
301 836 610360666
320 735 24127012
150 584 57560938
30 128 144008763
444 717 611612884
46 560 950226224
616 922 325087503
209 876 754214429
118 1000 596998542
7 348 670148631
427 1000 426675748
459 676 662731381
471 543 802596322
592 754 455206138
377 1000 535730764
45 1000 246434464
163 240 409295376
693 911 677097335
116 507 310050331
439 818 978623118
630 766 8795642
400 440 799084503
772 1000 356052078
419 682 728595493
441 815 800730166
72 328 852318972
596 647 531356768
308 514 564477035
332 816 570303778
590 819 205898516
30 576 674197692
308 595 288448890
335 349 953287759
295 465 133829598
297 470 995127699
387 701 842782228
168 528 852538047
101 176 348238530
363 824 161746005
646 695 896169439
154 356 502204265
287 500 927761035
513 728 586862854
314 635 775686741
500 738 540988981
275 917 603917041
3 560 142389281
889 1000 635829587
471 573 81816361
57 460 222574049
308 645 498304985
741 745 717259063
179 485 138930195
230 728 943963094
175 797 170480690
509 1000 816757607
227 797 647330201
206 610 737973505
344 508 414393855
529 739 633884227
483 910 733935944
213 977 549661757
314 471 66409428
303 451 237519833
51 368 892238730
314 590 494395507
286 337 667994480
161 411 193400477
673 881 711784868
363 766 463545922
126 719 184588586
38 381 945822248
46 740 460393134
454 713 932665651
906 1000 463696154
950 984 973982294
96 521 428825306
610 628 705025745
110 448 151259400
232 970 315980716
500 795 715462855
613 726 154907650
525 813 123342549
171 1000 134754126
121 252 676046850
433 679 464656204
184 836 959365775
604 994 449553980
424 1000 110024245
443 664 170471057
46 986 515608919
734 789 939536982
65 1000 893870296
104 955 614363810
208 569 260190920
632 877 497827894
226 1000 117095670
95 113 446475888
363 745 653356992
629 904 9060508
98 607 445366297
685 966 420435682
790 858 76081843
446 682 185764548
22 974 553917486
471 514 373490010
257 1000 181308214
754 947 529595685
520 978 707594290
905 977 230803760
616 943 169211851
122 540 47725065
539 939 563010780
102 527 857933358
545 745 858386467
712 719 894260665
331 460 682739750
808 990 212988312
593 1000 900085182
507 573 762305781
740 806 871733457
429 656 291373034
374 597 82887687
202 693 216127341
361 606 418305972
112 232 723006715
478 738 616471238
468 679 359167152
754 892 789911297
41 990 920957644
501 725 913041338
158 601 210577773
428 943 77148261
947 964 641351383
262 512 241135504
16 699 760343555
460 624 993782338
706 808 167754990
676 976 533248823
177 617 785095752
28 281 527631920
340 751 861372613
133 655 761435648
77 882 925860190
62 143 27100338
4 806 885904707
95 794 204029066
739 836 936462169
129 745 470984126
777 1000 588415615
415 804 995698310
68 439 321306337
256 569 544291871
102 765 967627868
191 471 731828628
814 947 630212746
120 722 592649279
539 705 11109083
501 604 850707069
521 705 709834464
716 947 492640469
468 944 891656767
206 748 975888321
543 647 37449142
284 776 513547163
153 267 882851824
545 771 675360850
744 787 412546202
314 892 721498872
122 932 788607869
543 892 425443408
647 678 146884744
461 514 616212528
484 899 153217243
314 637 932632720
245 545 413552528
343 833 567415179
288 687 133642435
740 800 206244796
255 863 240185717
630 808 526844110
202 694 181778028
249 838 477408838
474 765 886759874
198 267 377484684
844 947 343961023
58 952 780417178
555 728 186391092
58 438 683606825
667 951 270067337
449 510 621759625
405 1000 805536149
242 663 493423465
157 551 643427250
654 671 896276812
31 542 147413231
647 814 931909397
396 716 481970625
252 986 527063738
202 252 158646935
507 740 192138394
511 765 943907838
399 463 364692522
31 128 14341713
392 740 943731297
449 737 881771251
710 948 192836313
321 895 15560437
278 317 496359978
487 603 525181505
207 982 373858443
292 840 671604144
86 283 62351720
239 842 777527436
374 569 107221983
122 609 880795498
235 609 958440267
67 116 595311015
84 600 476142516
471 674 947476815
57 739 427090263
82 457 784556524
396 1000 932337897
429 939 599646867
490 828 313238009
255 525 121134498
471 754 439998520
587 635 298369943
331 812 598045989
269 583 333076658
830 903 157391233
193 916 866147819
46 635 492442927
45 369 243769942
491 710 857141180
533 891 963262359
892 939 57346110
27 731 165757784
135 768 602074867
82 656 992418548
336 525 644632606
55 734 507735049
316 893 651485937
659 796 631592161
433 569 744289996
77 808 708559843
307 788 74009995
437 508 313803765
68 484 875430712
373 409 920620138
852 992 117596396
177 919 215137366
521 647 237365566
169 657 126706606
186 525 109808829
657 940 552105771
125 1000 292779200
660 1000 958507215
418 446 430870557
95 575 778180589
468 598 492393316
111 816 996028030
680 1000 109053131
487 726 330194020
496 516 106978400
109 540 864161687
154 430 363841604
301 568 333475003
146 893 190675358
175 974 229715651
372 752 951855555
937 966 658503735
272 873 560967655
672 981 346958197
483 1000 353208491
138 213 643810848
190 332 499860048
26 138 871174885
513 788 79550893
683 754 664462415
569 701 60908533
46 148 910322450
116 545 431389587
678 947 500505376
27 48 601412364
591 675 362813856
582 744 259558666
125 247 772409310
576 713 639279088
351 636 677459184
25 1000 5286025
705 745 118888163
646 825 294385465
765 828 578767011
67 609 808228649
543 545 729886065
415 886 818994101
781 1000 926489131
139 308 637727291
177 982 587783499
924 1000 543664891
254 321 957123493
294 981 416533750
558 826 968117475
94 245 448424664
262 532 753534324
166 210 141865757
298 545 551688632
38 947 436225198
464 520 808988166
224 595 857127170
234 303 948553832
545 746 23093755
39 372 330996260
330 612 512826097
167 808 736929988
684 1000 282846774
149 433 480771675
740 814 553942797
5 552 209441029
64 541 78406200
452 943 720439401
301 508 901170851
961 1000 14094788
644 652 156195897
432 487 703033720
514 940 700046
10 707 781250768
949 1000 333154914
545 832 524831511
314 647 372572439
946 1000 556166347
25 553 588784837
306 412 311429280
754 899 424216353
877 1000 208747994
663 829 595766195
59 892 776317047
281 902 727028661
128 313 345812480
94 336 501355480
740 996 479996112
518 739 551167420
740 947 887409061
38 740 250380361
230 972 911591437
341 585 122788636
255 804 398320504
202 514 584314053
831 1000 937764142
202 348 625789058
197 369 892004247
246 751 435039259
15 543 346761872
455 700 968998989
381 808 36875280
54 825 606470606
314 423 791430421
376 563 545497534
415 887 444435063
208 613 391758672
718 1000 739355554
587 740 901709241
890 1000 137329138
545 819 817181782
662 717 366711279
211 932 607771883
358 522 539345821
98 833 598648607
126 795 928187539
672 740 416512965
993 1000 880116314
647 923 522424066
41 515 523274545
539 744 304439642
497 1000 374410529
651 892 133752885
568 902 808055807
483 906 999141957
207 830 672926287
829 974 265764084
471 896 265178220
471 760 835650334
230 765 269850156
46 745 625308785
601 950 521511018
242 501 62140553
243 632 931801741
230 564 303989661
824 923 472371173
251 677 95592209
382 941 115158744
744 921 729787148
129 754 154218491
306 1000 565868198
598 944 72036678
174 980 397309576
433 914 297642221
64 428 910329184
390 637 350277470
496 618 933327670
468 881 837430706
163 798 692681830
121 980 895842116
359 725 527284721
821 917 905817700
265 543 784594221
130 789 441420822
693 824 366200386
819 892 259507329
615 1000 898981339
154 1000 188849849
745 947 201751628
288 463 576562158
215 676 109020756
543 754 504826364
466 485 817967176
911 982 435458204
46 195 109622179
530 894 336712609
53 634 729811535
314 521 620592797
78 332 140507094
94 520 950359341
62 762 802672388
561 675 975453005
503 546 192178022
520 713 633229383
634 732 100437973
363 585 631160243
836 950 462990503
554 709 452771053
628 701 850769953
478 569 353036094
140 695 641008939
256 687 542305897
240 694 408181679
363 471 963257572
569 610 599415768
483 522 410794397
6 357 411052321
506 972 968185250
687 969 926499993
18 1000 740558543
447 543 824480910
30 77 466008060
217 419 40298966
572 909 883054769
639 695 743823850
102 512 981265203
514 629 381956985
297 430 233555258
27 995 787749739
29 621 536763335
10 116 141173019
582 823 56195243
284 639 827493871
800 921 355045565
904 989 888209276
545 706 12462430
116 543 121000096
292 418 167715668
523 673 621843856
64 374 651906937
160 711 624563470
766 921 334648115
144 573 160856206
49 335 229974841
543 947 356256214
631 676 691269779
115 178 832240901
673 888 223498062
581 780 296922801
844 970 955832007
23 647 685532912
170 947 181579884
28 526 895382312
46 413 347756938
64 863 271358746
45 785 238903289
761 763 822576404
416 705 481978720
122 573 376976488
568 798 564804159
657 774 106423808
213 639 90571658
297 365 514707383
512 616 474404965
295 894 938931697
438 635 927706209
210 397 460747766
505 545 637382938
46 841 715850009
81 690 811666681
387 535 145799629
314 539 478734104
24 817 131799877
89 720 480247702
788 878 263692779
998 1000 604155360
211 543 105821174
41 543 330446515
28 399 710984410
340 411 720328901
75 636 950488254
40 823 433624654
345 730 590632988
590 837 35845571
484 590 40012231
647 745 54552809
123 863 118445256
183 314 693512396
351 812 294168543
543 590 23627339
48 866 231245160
346 490 975011147
38 503 598073439
483 769 616922576
754 766 443002519
690 824 515028262
137 872 122657332
328 1000 911947428
201 797 160147905
540 921 197341694
960 1000 657005351
314 339 490129180
672 947 67373456
88 1000 584753121
245 940 725450423
561 628 337423033
41 545 991065895
388 792 381989606
352 656 886865243
518 609 690499399
52 774 708751507
604 902 604056138
292 325 290501663
627 963 444360979
234 320 575899389
507 543 974483282
79 318 433253240
22 986 13089362
122 725 302195804
177 255 507376646
3 659 366808798
36 717 349479942
232 591 435823234
591 932 251925016
90 985 664533690
532 969 225284347
728 798 507697319
503 981 84693499
3 722 484259963
126 856 954687968
811 1000 135072405
350 499 834587229
3 336 411126659
207 300 351824422
119 257 96921608
934 974 774825038
201 208 95803468
374 490 821935400
545 705 685625185
152 728 116754739
46 883 871993564
624 962 913116168
230 726 914107989
441 445 685186403
164 915 709673913
62 155 53339436
472 972 536085564
3 30 997814525
31 341 630691905
163 627 926418408
837 899 506311470
337 616 410710096
307 853 75217868
500 513 239700720
229 720 593243369
174 630 485536520
647 740 57927324
71 134 471016097
56 289 247633944
238 950 194912873
659 928 658256963
314 461 270251405
90 778 256951932
888 903 905278472
601 882 914618231
115 1000 706946498
287 531 523156375
559 688 300643018
916 917 362990934
96 540 749273050
111 930 240286204
267 843 965048483
452 616 618739394
586 734 314170072
857 1000 555638092
465 601 716894406
823 974 591302334
272 314 394517939
71 513 879895827
300 415 409867895
68 234 449933181
967 977 87185528
449 1000 251072576
56 214 384242243
695 867 348995956
208 568 722825476
601 911 420991791
292 663 675030422
71 341 995004671
128 663 870306671
14 1000 601924037
296 631 685879752
106 529 195751338
281 658 550610622
347 740 679423201
208 618 429560856
740 754 686295188
744 939 607054412
266 804 545151342
54 494 506456657
460 618 206653582
313 315 306682715
346 610 348815717
623 754 122442067
267 385 646399273
240 460 666266539
208 700 750215670
628 797 257029124
696 849 665877215
228 874 480677783
643 1000 304186815
834 861 700349030
587 745 934331455
145 531 98106943
279 685 477074972
300 919 154570110
120 542 447067152
7 245 611777439
321 856 33610683
601 921 785006784
842 993 547959134
344 728 259649680
839 1000 159124809
443 587 543907457
834 854 517899194
239 637 270560261
269 588 626214911
622 957 1116446
67 429 214940250
144 252 801443758
103 612 929082099
125 809 186519299
24 134 710008201
257 767 527419345
230 804 428598064
106 695 860752366
494 589 867313824
6 316 535447360
155 931 870253141
12 1000 725867533
22 431 914017164
186 978 963335219
281 659 13838238
296 362 413920568
368 928 581602922
23 745 210714474
265 744 880800743
194 215 449040094
686 804 161198770
745 838 810847592
566 986 632386938
360 848 840342415
388 570 293550081
842 1000 860603657
568 852 991175010
340 998 157189305
545 817 581708275
630 830 646436535
26 47 509002048
507 990 505946344
211 630 203550504
471 947 936460564
67 745 753122163
227 899 422054441
25 941 78967658
429 725 553080768
552 1000 367763864
110 623 605858020
141 339 931701615
170 740 980848900
206 738 18727210
471 841 448583175
997 1000 598744200
168 591 855460748
111 745 928849743
65 834 768093041
167 800 16288707
545 899 624896410
213 797 785469973
532 591 445998935
442 648 690946999
67 443 264225848
512 812 414794030
474 801 610022209
526 963 228900169
740 819 61924940
40 518 111180823
333 512 223109118
307 456 34374308
531 701 390074958
801 881 776302414
446 774 444291789
142 948 813892767
380 387 46153851
647 754 336225149
242 651 683129849
10 24 853021808
138 851 765513559
315 618 394003804
373 514 452071394
342 795 311803018