rt，真的绷不住了，挂在 #5~#8，#11，#13

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
vector<int>v[N];
int n,m,fa[N],dep[N],sz[N],son[N],top[N],id[N],rk[N],cnt,w[N],tag[M];
struct E{
	int x,y,w;
}edge[M];
bool cmp1(E a,E b)
{
	return a.w<b.w;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs1(int p,int faa)
{
	fa[p]=faa;
	dep[p]=dep[faa]+1;
	sz[p]=1;
	for(int t:v[p])
	{
		if(t==faa)continue;
		dfs1(t,p);
		sz[p]+=sz[t];
		if(sz[t]>sz[son[p]])son[p]=t;
	}
}
void dfs2(int p,int faa)
{
	top[p]=faa;
	id[p]=++cnt;
	rk[cnt]=p;
	if(!son[p])return;
	dfs2(son[p],faa);
	for(int t:v[p])
	{
		if(t==fa[p]||t==son[p])continue;
		dfs2(t,t);
	}
}
struct node{
	int l,r,val1,val2;
};
bool cmp2(int a,int b)
{
	return a>b;
}
node merge(node a,node b)
{
	int aa[5]={a.val1,a.val2,b.val1,b.val2};
	sort(aa,aa+4,cmp2);
	node res;
	res.val1=aa[0];res.val2=-1e9;
	res.l=a.l,res.r=b.r;
	for(int i=1;i<3;i++)
	if(aa[i]!=aa[0]){res.val2=aa[i];break;}
	return res;
}
struct Tree{
	node Tr[N<<2];
	#define ls(x) (x<<1)
	#define rs(x) (x<<1|1)
	void pushup(int x)
	{
		Tr[x]=merge(Tr[ls(x)],Tr[rs(x)]);
	}
	void build(int id,int l,int r)
	{
		Tr[id]={l,r};
		if(l==r)
		{
			Tr[id].val1=w[rk[l]];
			Tr[id].val2=-1e9;
			return;
		}
		int mid=l+r>>1;
		build(ls(id),l,mid);
		build(rs(id),mid+1,r);
		pushup(id);
	}
	node query(int id,int a,int b)
	{
		if(a<=Tr[id].l&&Tr[id].r<=b)return Tr[id];
		int mid=Tr[id].l+Tr[id].r>>1;node ans;ans.val1=ans.val2=-1e9;
		if(a<=mid)ans=merge(ans,query(ls(id),a,b));
		if(b>mid)ans=merge(ans,query(rs(id),mid+1,b));
		return ans;
	}
}T;
node query(int a,int b)
{
	node ans;
	ans.val1=-1e9,ans.val2=-1e9;
	while(top[a]!=top[b])
	{
		if(dep[top[a]]<dep[top[b]])swap(a,b);
		ans=merge(ans,T.query(1,id[top[a]],id[a]));
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	ans=merge(ans,T.query(1,id[a]+1,id[b]));
	return ans;
}
int main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>edge[i].x>>edge[i].y>>edge[i].w;
	}
	sort(edge+1,edge+m+1,cmp1);
	for(int i=1;i<=n;i++)fa[i]=i;
	long long sum=0;
	for(int i=1;i<=m;i++)
	{
		int x=edge[i].x,y=edge[i].y,fx=find(x),fy=find(y);
		if(fx==fy)tag[i]=1;
		else
		{
			fa[fx]=fy;
			v[x].push_back(y);
			v[y].push_back(x);
			sum+=edge[i].w;
		}
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		if(!tag[i]&&edge[i].x!=edge[i].y)
		{
			if(dep[edge[i].x]<dep[edge[i].y])w[edge[i].y]=edge[i].w;
			else w[edge[i].x]=edge[i].w;
		}
	}
	T.build(1,1,n);
	long long ans=1e18;
	for(int i=1;i<=m;i++)
	{
		if(tag[i])
		{
			int x=edge[i].x,y=edge[i].y,w=edge[i].w;
			if(x==y)continue;
			node res=query(x,y);
			if(w>res.val1&&res.val1!=-1e9)ans=min(ans,sum-res.val1+w);
			else if(w>res.val2&&res.val2!=-1e9)ans=min(ans,sum-res.val2+w);
		}
	}
	cout<<ans;
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}

#5 数据：

1000 2000
677 507 5109
168 742 3365
125 854 771
875 399 207
554 762 5761
162 238 7217
95 8 7206
803 282 4092
146 953 2423
455 348 3365
843 561 656
616 414 6669
949 917 479
355 164 5315
76 372 2976
114 400 1013
403 952 487
722 556 2451
932 837 7449
62 242 2713
582 388 7821
860 177 2429
477 245 1825
583 771 2750
349 609 3458
650 145 3867
542 88 2869
900 260 5766
85 786 7160
808 276 1518
432 818 4881
536 253 5633
888 585 3826
642 342 5874
57 549 6884
79 441 7812
306 578 507
828 789 6167
849 281 4087
405 35 3663
231 679 2965
950 2 2473
752 8 969
344 577 3663
64 813 4285
88 743 4711
653 203 6492
342 788 5857
875 824 7548
158 17 4330
775 580 3892
518 430 1860
966 298 5515
324 872 3070
517 561 1982
228 379 5146
767 469 7175
810 322 7860
667 843 2895
140 255 3914
802 560 4072
208 830 3877
93 55 1294
581 925 6214
542 66 5132
396 562 6777
111 774 2401
363 481 6492
70 644 909
429 307 3361
277 462 3233
927 241 2262
429 739 6097
601 407 3158
535 168 2067
6 709 1934
799 959 944
212 136 2611
234 107 5533
366 784 5874
300 309 1837
746 830 3616
421 553 4087
199 426 1853
164 212 2307
178 585 2906
332 569 3703
126 861 7121
998 29 3814
393 56 1804
54 852 1456
404 868 8025
523 345 7382
874 65 6629
255 723 6415
565 756 6532
585 766 5453
288 805 3867
696 467 300
249 714 7625
723 826 2169
196 75 5261
203 486 3343
738 558 5874
232 89 3032
767 733 3227
911 580 6167
936 996 1401
726 968 1639
559 973 7602
356 383 2401
684 438 445
133 60 3330
105 649 390
863 193 4709
968 703 6127
58 26 6036
410 992 123
868 459 3877
166 566 3200
160 86 3073
602 44 3249
102 242 2086
859 273 4330
271 631 2686
715 616 1934
813 503 7008
275 848 7699
305 857 6619
453 768 95
884 401 65
328 652 858
965 402 4314
559 255 2151
663 463 481
248 360 815
78 904 300
506 319 2473
875 44 5109
244 425 4671
726 360 6370
477 369 5766
290 148 73
963 938 191
262 659 5533
453 145 6879
16 717 73
740 717 6846
166 279 4284
793 193 4071
130 185 2513
263 641 4140
688 623 3363
13 399 2990
127 556 3852
363 160 5197
739 963 5874
327 351 6453
312 153 2965
146 282 4202
350 328 1555
589 620 3119
456 767 5170
951 399 4044
649 817 309
569 174 44
670 343 7479
909 917 3388
277 248 7008
259 713 677
660 952 1173
623 228 1155
604 311 4635
106 42 7234
132 994 5614
286 870 837
973 776 4140
206 913 2149
516 485 3098
91 724 6452
221 813 7922
911 577 7668
928 34 4273
177 938 1239
246 786 3281
406 313 2318
812 521 4391
402 516 7668
127 916 6547
595 167 2423
670 560 3505
17 497 4103
151 137 6774
41 659 6059
508 558 386
772 483 3010
938 414 1945
968 996 2513
10 212 7338
388 608 3119
13 545 7514
738 842 230
242 682 6331
538 405 2636
805 435 6846
400 630 8012
771 747 5785
948 555 2948
417 17 4292
470 154 6894
290 591 4721
277 810 6974
837 409 578
275 268 1934
47 260 972
626 101 57
720 644 1464
562 811 950
4 648 7123
299 965 5813
976 150 972
258 859 2843
511 251 2713
60 523 4635
569 699 5373
15 1 142
732 132 5391
332 645 5857
72 216 1013
641 107 7989
676 366 5116
723 790 6974
765 767 6492
257 505 2329
535 462 4287
149 566 2013
614 458 5682
985 757 5221
65 763 7479
810 443 626
68 260 4863
414 577 3135
731 243 2151
738 220 7123
706 469 3119
132 518 5460
113 173 1773
41 486 445
34 225 3119
875 727 6683
499 44 3732
255 839 6311
282 817 309
673 829 2401
617 422 7668
514 938 7245
956 308 2085
189 778 384
418 62 2202
516 801 7393
444 717 300
585 561 2990
858 936 1464
369 755 103
276 408 6600
2 432 6657
932 43 6167
778 742 5761
931 612 6777
494 577 2429
599 888 6262
85 894 1271
630 104 4166
192 745 914
126 22 5741
628 302 7382
160 67 7777
158 746 5261
35 967 4355
848 416 1036
71 291 5132
467 601 7257
865 73 1837
261 478 7205
943 174 1777
204 815 6596
895 823 3296
707 73 864
491 631 6669
486 494 3505
641 35 868
480 944 3814
131 534 7338
627 446 4238
784 384 3494
4 227 2869
410 734 5594
440 13 6370
732 426 626
783 127 6893
853 806 207
1000 842 3661
304 460 3233
536 463 2513
175 474 7160
12 264 3158
70 327 4140
712 752 3852
535 444 7977
384 257 4575
622 667 3273
669 755 1633
887 113 3093
83 816 5460
995 870 6036
692 758 2013
881 896 1202
815 996 7382
795 782 68
110 183 7044
955 816 5861
343 767 5941
547 802 6894
170 15 3892
682 824 2151
479 403 5392
239 159 2897
144 776 5249
600 721 3465
515 411 2353
959 328 3813
224 23 6763
380 532 7602
801 529 1574
162 740 5547
32 321 5132
256 962 6059
774 571 4255
24 381 6148
588 226 2764
190 657 6596
195 588 3187
145 416 2149
58 292 671
797 388 5857
181 576 573
26 109 300
302 221 866
322 244 7257
80 671 5202
212 527 4330
265 670 7121
29 35 3187
905 426 1574
200 502 6098
596 634 5874
918 539 2151
366 900 1860
474 558 1732
75 281 2782
765 591 7796
874 112 5197
240 55 6225
510 781 1003
857 389 1974
93 67 6783
63 481 7220
379 419 7547
928 132 6803
148 787 235
942 225 4292
378 866 2611
204 569 3616
576 863 2602
266 897 7175
956 439 6909
68 419 7625
493 595 8073
158 305 1864
716 101 366
465 949 3343
494 868 7338
23 720 1318
644 581 5815
429 648 4813
273 375 5633
966 166 1779
505 771 3705
859 590 2114
246 1000 6694
38 389 2401
521 935 1085
73 92 6856
978 466 4037
594 18 6520
812 56 2067
133 691 5486
403 508 6492
839 318 2075
866 742 3298
801 951 6596
868 709 7943
818 109 4726
118 89 1626
211 53 7111
202 82 1919
142 834 6674
913 505 7570
668 683 4971
871 730 5132
941 151 2602
901 47 224
440 320 6148
567 548 1013
53 717 2857
822 577 2069
122 519 3135
143 260 1677
66 587 3661
191 41 903
138 769 184
546 405 1837
923 560 6666
526 233 5009
190 543 3060
672 945 1493
754 715 7877
40 931 3071
26 450 6214
160 894 8073
566 717 2906
386 745 2879
930 363 5614
218 539 3597
417 572 2782
599 354 1356
540 863 2538
199 188 5309
830 302 7160
415 727 1860
783 608 418
387 250 4966
476 462 7402
430 685 5614
645 831 65
493 33 5155
55 894 498
748 113 1003
112 962 7902
904 357 5536
124 510 972
831 131 1523
902 8 1837
271 737 7625
154 731 2157
549 765 5246
278 481 5658
605 714 5547
32 117 3588
978 698 4284
794 212 341
504 97 1853
116 12 87
48 612 5913
83 699 4405
659 849 7297
203 709 6127
615 93 1128
679 538 794
555 330 416
541 376 4285
254 73 2490
840 81 6125
791 949 2220
355 647 6191
679 65 4711
466 534 4529
510 818 7114
655 26 7668
784 645 7256
136 694 7977
462 448 6559
504 365 5533
408 782 4314
348 967 5772
330 35 4203
447 738 3361
581 849 3388
830 696 2470
96 868 65
153 717 317
86 175 5559
614 511 5197
147 497 602
203 630 7256
884 86 5463
456 301 5633
666 812 6532
946 926 5761
262 192 3263
15 363 4779
436 20 1864
83 637 5676
209 713 3826
449 97 2237
7 751 5977
316 835 7829
572 300 1184
989 141 5642
24 866 977
612 608 615
603 850 2322
829 268 2151
210 994 7704
511 260 5392
420 568 3823
129 56 1915
890 910 3877
328 966 5547
848 186 5941
84 548 6331
969 586 1773
42 253 5515
876 138 386
21 888 7205
355 958 7828
896 625 6515
471 317 6821
425 543 4067
851 15 2157
695 646 7399
894 288 5440
134 509 5132
713 257 6181
675 235 2897
642 940 5486
209 322 4631
42 44 5392
844 181 3088
991 80 7821
873 107 8035
926 208 390
790 684 3294
676 894 3517
676 620 5992
476 896 6669
240 218 4579
419 516 2451
825 649 1488
245 959 6120
996 745 5486
852 840 445
722 14 5901
991 174 3273
221 585 1474
201 558 2659
469 305 7205
407 125 4709
388 763 5481
479 134 1318
985 751 73
861 568 671
134 110 7557
970 913 7759
631 374 315
558 633 5481
361 439 4087
460 713 1773
123 494 1657
780 317 2991
323 525 2812
977 586 935
408 937 6488
101 786 2291
648 335 6909
395 287 3187
531 821 6803
458 992 6225
794 896 5536
316 656 2237
116 229 5797
606 826 7570
551 65 4737
131 429 1184
126 127 3283
310 48 479
587 927 3494
185 913 1594
175 567 4089
741 535 7202
496 339 1837
903 91 4314
382 24 1239
43 916 1915
213 890 1178
60 386 4552
573 348 7382
253 261 1750
168 210 7217
923 785 4436
893 16 3943
832 61 5515
412 307 2768
30 652 7600
928 580 1670
912 576 5547
272 344 7200
280 862 580
584 407 1424
428 530 6056
307 485 814
1 996 6308
338 883 5222
891 689 3363
321 302 5509
63 671 4852
700 760 3073
594 713 771
952 916 456
321 574 1633
187 957 1864
582 925 95
725 549 866
261 713 972
999 835 182
862 377 1047
593 171 837
178 744 6491
388 519 5037
20 868 1294
623 428 5404
423 277 1493
91 809 2664
330 977 1178
702 849 1215
431 834 1934
408 57 1686
596 627 456
939 551 7860
932 733 2262
176 845 6418
268 146 4368
662 287 5463
786 713 2291
707 15 4460
41 256 4285
45 914 5009
549 819 5547
230 476 1442
643 389 2817
105 973 5450
399 88 5309
215 129 7517
27 299 866
844 989 7039
757 273 6167
906 70 1896
383 60 3852
741 2 3179
300 908 7791
418 1 6067
411 622 6389
368 377 1178
450 19 7838
545 79 1953
974 990 7293
351 968 4534
604 888 5857
565 63 3852
545 222 4371
529 527 771
726 50 5197
208 508 6453
182 648 1871
653 106 6515
228 870 1085
252 269 909
50 849 6763
138 183 4203
201 833 4552
268 161 4436
965 52 3914
804 825 3394
162 454 6693
345 781 1686
572 514 4248
379 411 7810
248 181 5221
568 29 3877
236 534 366
273 942 1474
433 517 1125
772 481 6487
457 109 6590
666 150 3071
371 99 3663
775 9 7517
969 618 5901
983 874 7782
151 787 2636
335 496 3494
992 380 4238
984 52 8023
659 881 2022
328 430 6516
935 306 2308
501 884 6973
489 647 3119
591 780 5246
461 380 7114
69 653 6715
192 863 5626
81 916 3363
596 347 4248
652 532 7111
231 51 4474
90 839 5530
605 286 769
65 551 282
96 127 4368
272 229 386
897 679 4044
631 839 5037
899 761 4916
630 465 4314
852 43 6774
900 710 4844
164 567 6011
953 379 2099
563 754 206
759 237 4140
48 84 2307
550 339 1447
74 291 7355
705 11 1065
747 405 261
699 269 7547
975 608 1447
871 751 8073
313 286 2237
959 281 7256
879 998 1838
689 674 1982
532 905 5392
423 643 6966
100 155 7644
271 360 4811
627 658 2701
209 438 5197
828 649 6191
609 308 3505
353 221 1574
888 965 4965
777 106 2834
247 643 1953
397 178 3093
127 137 6520
968 625 8012
641 963 7829
20 141 5509
357 543 5463
50 210 3740
431 301 6452
88 50 7479
194 664 8025
541 175 6798
176 863 4551
451 798 498
726 14 6453
970 836 7200
513 465 44
997 53 1670
847 72 3135
237 13 5315
954 35 4087
384 220 6881
415 309 4765
803 927 7557
567 221 7604
717 35 4000
788 875 1838
571 705 6491
724 92 2177
699 21 2879
229 986 6191
681 262 3555
755 261 2092
743 967 6515
945 403 5676
81 122 6774
605 486 7516
765 625 7922
845 761 7782
365 631 1118
612 595 4330
828 562 4166
411 366 5105
44 720 496
260 679 2170
337 229 7257
770 558 1633
883 897 7473
462 22 1442
578 30 7738
30 896 1549
472 159 2513
768 393 671
264 282 1800
816 74 869
379 577 6056
894 763 4650
954 16 1302
112 380 2371
662 905 6731
364 174 5826
369 100 5385
426 141 7777
608 959 765
285 299 4966
18 34 5761
611 282 2636
369 856 5614
796 168 3590
318 452 5315
407 44 7633
130 93 6902
167 714 4087
239 407 6849
175 927 3131
806 602 3852
718 373 936
581 512 5273
423 184 5658
533 256 6669
167 920 8092
756 84 5387
545 904 5105
779 252 5314
987 452 1313
742 817 2359
173 486 2318
770 122 7602
314 195 4507
958 786 5197
159 765 3628
972 29 1945
934 132 3505
871 22 3113
885 615 936
575 281 381
805 866 235
701 368 7157
568 150 6056
443 546 5703
913 29 479
206 256 6997
531 812 3872
730 792 4552
606 889 4355
571 728 4784
711 36 3031
594 81 5170
621 463 7220
695 977 1294
931 507 4529
45 786 2308
399 566 1353
68 254 2022
758 379 3656
714 973 3437
901 634 6488
918 1000 6701
781 892 7157
493 257 6181
598 526 3283
20 266 6012
819 784 7245
112 848 7842
840 793 2274
833 732 5387
849 8 2636
132 104 87
227 127 3298
254 538 7510
815 528 1919
209 656 8054
39 44 282
31 135 731
485 48 5874
207 812 2048
710 476 941
141 559 7175
647 432 3877
297 551 741
560 986 4575
764 824 3494
835 991 3626
356 250 7217
452 880 6275
323 22 4314
775 129 4613
176 585 6214
605 786 6244
721 620 3879
249 450 2291
497 996 3790
660 157 4159
485 775 2906
916 52 6059
828 650 2202
308 847 5116
530 227 7012
864 745 1202
317 771 4949
491 526 6181
309 153 1294
454 92 2664
298 873 4045
439 157 888
558 769 1518
427 432 6893
728 555 4949
557 577 694
325 749 2262
882 587 3555
826 412 4529
507 399 804
819 641 449
7 429 6933
434 313 4514
90 575 4554
86 153 4045
291 706 309
437 569 2451
198 293 2307
62 347 4765
910 438 3270
931 711 3520
873 786 5392
475 294 1353
319 623 3626
331 598 5632
364 209 5569
89 174 77
128 99 1118
683 831 3872
240 294 2274
270 443 1838
740 622 6940
374 260 456
135 746 7210
753 823 384
222 864 5924
924 77 300
267 860 4044
993 223 2401
322 328 3294
874 774 743
973 554 1135
547 155 7883
869 800 972
186 272 3710
980 788 794
614 156 8035
172 893 3877
989 361 1178
346 654 5826
992 336 2401
537 220 3656
385 908 5463
314 920 95
919 514 1838
155 495 4965
571 93 3131
763 775 1135
126 744 7449
193 818 6619
205 737 2783
664 363 4551
99 259 6515
268 866 973
624 550 35
334 52 1488
100 998 1125
125 27 4601
916 835 3388
792 707 909
900 169 2857
921 602 1135
174 268 2318
95 72 2990
770 293 6221
251 653 4248
367 8 7532
861 858 4765
820 976 3394
254 305 5440
77 409 5536
921 736 6902
64 641 806
174 866 4890
892 353 709
49 686 3748
235 612 5435
336 975 2329
549 753 7123
385 3 1155
75 662 7547
635 539 3320
939 416 1518
888 711 6097
392 155 4278
242 307 3179
867 731 6893
299 984 894
106 309 1353
326 518 7121
807 454 3361
108 543 1825
860 540 5132
965 144 5874
135 776 1523
293 737 6444
163 875 7930
373 718 6124
185 69 7902
380 275 3775
984 829 3879
872 779 6893
10 319 3073
754 996 3294
46 133 2429
470 329 1101
60 386 2895
762 194 1456
18 145 4248
636 486 765
473 972 4192
974 301 7111
703 720 771
912 286 1339
917 444 3914
435 379 4044
654 963 6167
932 215 5735
737 784 4192
628 417 4053
452 648 2114
549 983 5633
298 62 6011
563 136 6369
357 595 3590
664 634 3661
509 30 6418
776 9 1118
263 746 7842
728 686 1125
603 810 5533
45 428 7217
236 724 4460
469 805 7225
889 225 1804
870 29 3616
652 115 1750
487 69 456
46 622 4726
898 835 3524
877 464 1523
637 750 3971
1000 810 4730
955 21 35
19 165 3555
709 232 7976
599 475 4853
414 645 7995
466 498 6721
818 543 3376
878 314 3365
346 277 1698
119 535 4044
661 966 7924
59 167 7333
817 561 1945
90 979 2085
749 45 4037
304 500 4727
665 374 291
528 306 2812
968 629 5225
237 181 298
519 429 3877
525 547 6657
798 850 3263
751 171 7989
512 351 2812
3 936 487
241 859 8073
574 633 4890
835 585 4916
878 285 5861
104 872 1670
763 257 7200
607 142 6694
68 704 5460
597 343 2919
548 10 5875
251 85 1464
305 501 5223
461 820 5246
789 568 3628
430 628 3071
365 500 7007
389 558 3325
573 907 3943
211 352 6803
658 221 5941
662 767 1173
129 251 6547
114 948 5555
212 121 5824
183 157 3755
327 771 100
992 813 6559
41 697 4498
456 825 709
253 777 7738
658 214 1879
898 602 4314
903 689 3275
427 992 2834
639 731 366
223 92 319
407 679 2948
281 216 3946
320 76 2906
624 146 7399
139 219 1271
712 347 5741
456 781 4469
668 697 8012
502 553 3796
303 563 903
976 984 5804
165 951 1173
765 35 843
527 789 814
767 394 6974
651 461 2897
623 552 7402
657 576 2220
478 53 3010
690 769 1294
780 24 6783
194 750 514
364 903 1401
574 282 6966
422 688 221
481 608 858
736 605 6803
470 667 5766
17 770 1974
238 816 7782
755 491 6373
827 554 7171
739 646 4858
18 266 1354
140 514 4405
336 850 6440
955 674 6415
184 292 87
591 336 2202
220 16 6492
461 287 6757
227 236 5374
646 24 580
994 546 2697
398 296 3656
661 596 3879
918 452 4784
823 275 3705
28 742 2237
279 854 4405
911 193 2318
450 863 3200
299 321 4220
412 793 6115
682 505 4507
119 457 5569
84 817 2353
730 424 3273
570 97 4918
850 461 4103
937 663 969
98 473 2329
334 716 6222
220 525 3209
679 844 6849
161 200 1125
610 79 3613
691 389 898
27 252 5391
599 457 4863
226 997 6674
933 975 694
557 266 5435
35 713 3111
294 558 1879
983 153 3271
488 64 4631
605 742 6666
315 952 3796
311 711 3663
639 136 6225
759 11 5481
720 234 5450
963 402 7402
745 863 3764
404 44 909
556 300 5763
165 765 5339
226 527 1633
672 853 4727
338 452 626
9 62 4730
90 689 7821
880 896 3330
100 138 7160
703 552 5314
687 214 3597
484 570 2220
548 188 3892
766 16 3273
22 594 2633
417 740 7039
654 745 3852
758 93 6976
69 551 741
250 553 1864
571 695 6299
812 832 5761
628 232 7044
930 325 4368
243 53 3255
338 961 4089
856 713 2764
121 271 4489
238 228 3879
61 279 309
58 622 4469
181 589 5633
511 950 5223
958 174 2048
450 721 4159
25 175 941
21 517 95
564 556 7245
619 936 3273
680 570 6488
773 648 5450
138 514 6191
490 671 4721
37 185 2262
735 523 4969
850 514 6827
110 422 7007
225 465 6098
693 504 461
476 188 2085
169 71 206
450 16 4575
527 558 6879
285 17 1184
363 153 1777
524 465 6963
222 713 57
970 268 571
79 241 4045
914 906 3555
384 849 207
482 210 709
774 38 1657
63 774 191
826 896 319
642 825 4089
945 29 3361
266 773 3787
167 621 866
331 909 1838
800 602 2069
867 957 3555
304 752 7206
913 29 7532
52 236 4036
336 858 6404
762 233 7936
638 983 1280
277 597 6100
71 934 667
244 432 2417
448 872 1246
521 680 7514
771 268 1013
196 374 2401
154 850 6543
341 222 6492
812 579 5460
242 712 7308
814 719 7550
744 104 6703
906 860 5569
620 243 3148
2 389 714
614 79 6144
230 486 6694
51 662 5083
372 282 241
785 945 1800
671 579 602
187 9 6674
779 205 626
810 424 6111
279 103 6933
35 3 6940
491 949 1447
355 372 2490
343 188 602
181 589 4655
561 35 2662
390 513 3949
638 168 5105
361 620 5515
596 967 6879
51 566 1934
368 350 5824
390 560 5515
117 237 7338
502 333 7829
625 184 4945
896 401 2636
590 551 1128
118 17 7402
152 807 1302
339 185 1036
809 463 3376
556 611 4192
927 101 7547
219 894 366
134 570 3376
623 327 7557
99 384 5626
841 339 3661
787 470 6011
458 972 3320
834 872 2559
539 101 4363
894 340 3732
190 720 6191
694 554 1464
778 916 3271
443 312 4836
656 411 3265
341 163 5132
296 202 2990
698 522 95
179 608 3294
76 992 4782
305 159 1398
342 185 5992
981 904 6600
495 132 4067
186 110 7732
962 324 1915
229 317 936
845 856 1657
342 702 1318
215 37 6669
213 670 6056
23 676 6115
432 419 1173
662 953 5826
596 993 6856
522 578 300
139 867 6446
53 301 4330
223 880 5547
371 683 6978
428 594 2220
263 907 794
437 266 6191
335 325 4368
365 149 4890
99 55 2787
265 137 667
440 725 4865
686 147 4089
603 91 7557
525 517 5875
215 253 3119
341 76 1626
141 578 2943
467 647 7297
708 566 1879
592 84 1574
25 561 7732
237 418 5105
668 19 2353
630 644 103
837 772 5695
483 669 3626
961 56 2318
493 679 5460
26 357 6357
374 325 4784
88 402 5861
369 809 6547
756 499 261
700 783 6275
235 863 589
771 535 6214
680 450 1915
520 974 261
108 192 6111
886 153 3722
293 713 849
645 364 5509
761 153 2473
440 317 507
424 271 2170
501 396 849
602 685 6650
645 380 5060
834 771 6127
346 14 7548
733 344 4271
967 566 230
991 941 5060
137 547 3787
200 400 589
267 216 4330
536 537 7902
443 238 5273
373 577 3249
82 471 3158
348 917 2513
580 56 2879
866 491 7058
394 681 5509
534 991 2092
31 536 4330
996 22 815
677 643 3263
255 765 1013
910 811 4784
416 501 6191
525 917 456
163 276 6940
217 158 2099
283 836 743
586 752 1302
30 34 5717
551 157 2636
843 528 4552
400 544 319
842 359 5763
417 896 6452
842 343 3330
883 426 457
541 645 4401
986 428 1488
613 580 1549
877 78 5109
833 625 771
890 608 7995
648 478 3943
410 851 4330
388 555 4625
463 742 2423
48 490 4753
11 951 3505
832 28 1101
306 123 4721
446 939 4036
570 913 3310
573 601 5309
995 445 4036
526 272 972
297 494 5309
817 689 6515
338 915 4671
907 832 4464
614 584 2092
443 108 898
437 793 6221
97 663 814
282 385 7952
543 264 3100
942 30 3570
976 702 4945
90 235 5626
66 906 6757
467 945 2306
701 692 3187
593 592 7308
373 685 4881
855 11 2306
492 73 8073
360 687 2523
994 435 7005
226 584 6262
806 103 6763
541 326 386
216 554 95
653 921 1703
9 118 4514
320 822 7976
5 291 1896
29 936 4865
337 200 1777
751 100 35
376 538 4067
226 283 7175
901 246 7479
846 221 449
572 281 4828
18 366 5992
256 842 1003
976 371 7602
176 740 3290
279 399 714
329 146 5789
865 780 6763
57 66 6543
769 817 2513
161 291 6127
210 239 4508
286 265 7308
222 211 5132
347 897 1155
866 281 4330
394 76 3281
575 607 7796
885 890 7264
568 898 5789
882 18 7777
930 554 2123
288 853 4713
538 777 4159
173 966 6802
678 16 1271
668 782 4865
938 990 7058
803 215 3661
857 908 5132
484 31 6763
928 38 7922
446 332 6881
36 380 298
581 348 6543
873 248 3456
907 761 5223
286 285 7256
195 285 5246
261 106 6125
68 758 6115
681 984 7838
295 153 1703
152 649 6418
409 817 3325
552 513 1339
329 597 7902
438 752 103
416 478 3764
825 43 5279
867 730 7044
525 552 5772
563 360 6559
648 806 7828
729 747 5861
157 652 3567
574 908 4314
333 285 6683
640 76 1919
556 486 898
120 815 7060
284 738 1125
163 458 2686
750 326 2965
957 936 2509
900 852 6559
976 507 6331
318 377 2022
466 669 602
292 556 1549
214 817 300
236 411 4554
577 938 6721
850 538 3187
401 538 1919
225 865 4018
928 415 5273
664 545 6532
759 903 2513
740 404 6516
206 385 5928
539 377 4314
171 404 3271
504 890 7342
686 690 65
127 636 4292
655 443 3764
775 999 6373
698 925 6775
370 286 6452
664 667 4727
86 116 5373
457 174 3705
912 343 6415
382 503 5202
495 238 4784
366 892 7123
584 824 4966
354 868 2163
276 30 3330
307 448 7838
43 819 7359
441 834 2943
471 145 620
534 821 6884
424 719 7382
634 658 944
117 486 1173
894 501 7902
466 807 6629
468 799 858
838 52 1985
733 888 321
961 52 5225
345 748 6781
532 323 3823
583 996 4721
824 282 2857
367 214 1633
144 714 8097
724 788 6461
623 51 4918
88 758 1639
964 178 3425
735 974 2685
668 772 7205
389 632 5009
168 513 5761
289 752 1135
409 620 6285
498 945 206
166 76 5804
103 93 3517
326 430 6389
115 166 8092
59 650 2220
459 580 184
940 364 8097
443 913 6731
301 690 868
606 133 3088
575 95 5116
854 601 2523
572 142 7225
861 501 4575
434 720 667
602 30 7597
150 286 1354
193 817 4071
370 700 2407
943 354 5440
122 484 6973
387 879 4067
55 669 6498
232 508 5105
278 241 1985
923 965 3031
553 663 2092
549 998 4000
813 867 814
523 221 2022
691 510 7123
870 622 4971
974 561 3394
607 882 2151
454 68 6957
87 499 2909
966 464 6978
925 454 390
505 816 6884
344 130 7877
172 88 5875
774 48 5884
947 538 677
657 741 5417
156 100 2075
629 821 2086
300 321 4722
781 52 258
743 24 6781
375 769 3465
770 783 4355
338 777 4087
940 476 416
402 785 1047
56 84 3255
358 237 6781
442 807 2322
67 62 5146
147 48 7989
340 53 615
904 991 2401
283 801 7704
255 342 6059
644 717 1777
473 678 95
899 243 1549
391 401 626
188 243 617
210 300 7275
727 991 1677
55 69 4405
533 780 4671
674 649 969
489 372 6415
162 108 235
53 700 5547
94 194 1934
234 843 2509
489 54 4087
719 377 3281
392 510 104
217 227 5703
295 291 7829
902 548 5165
292 391 5761
57 951 580
284 276 5197
514 886 1464
51 797 7952
852 196 7225
189 849 4363
663 219 7008
1 173 1125
524 475 3588
329 1 1825
791 639 5695
888 960 7123
367 516 4454
744 506 1135
732 142 7810
326 913 1017
946 540 3200
484 410 7860
274 278 89
503 820 1294
886 839 4417
137 457 5826
863 769 3489
493 825 3425
821 419 944
564 532 1067
296 349 6311
18 965 5555
286 661 4248
908 1 1670
239 974 6703
666 869 4529
617 583 3494
115 53 3456
663 548 4507
651 614 6415
490 966 620
988 616 3044
381 882 3626
989 840 5339
987 792 4971
37 697 4140
362 373 261
297 593 7256
233 539 95
729 197 2764
642 84 6856
602 833 6012
92 951 2157
210 56 2965
287 600 3456
352 134 1657
921 690 5901
813 825 5977
396 998 2435
530 661 3867
547 85 4072
211 506 3971
990 34 2636
33 713 241
760 914 1258
394 717 7774
328 231 4284
847 242 4464
752 502 7600
411 572 184
149 460 7548
757 787 1633
887 85 4314
136 292 1080
633 308 3343
189 484 7093
469 274 3071
616 536 2473
640 900 6262
589 894 4087
653 754 5316
269 567 1258
769 59 5273
196 815 5626
867 902 5807
870 644 4623
677 104 7485
351 907 3787
939 298 4220
734 985 565
981 147 3877
621 889 1135
818 99 5515
524 573 7936
782 867 7123
332 340 4711
177 757 6669
704 219 3656
541 713 6516
631 348 7828
712 641 4134
274 190 4287
651 23 4508
663 42 5092
926 691 6783
107 330 837
346 272 7633
909 261 6492
920 872 4045
782 57 837
74 840 207
701 485 7359
915 474 1800
979 380 1101
525 189 4166
578 241 914
671 612 5642
470 362 6856
156 819 4271
744 520 6167
956 168 7952
769 798 4635
525 673 4686
625 978 5826
227 346 5225
655 595 4498
155 984 2169
836 750 3113
424 911 7080
65 585 7828
377 938 73
913 488 6098
67 261 1246
990 722 7402
697 286 1353
645 155 7204
993 954 5202
306 623 5960
8 243 976
784 121 5992
109 287 182
413 247 1639
384 926 5901
740 592 2611
863 615 7039
787 216 3971
144 210 3661
15 443 7510
789 55 5417
987 853 4238
9 326 794
896 114 6488
145 719 7205
902 198 7483
971 181 390
984 698 6012
77 113 3119
618 83 1080
579 766 126
739 827 1318
457 261 5717
83 84 1698
533 927 941
80 3 3031
736 598 3179
960 200 1804
461 281 3877
405 451 7936
618 120 6098
562 849 6299
922 822 3740
464 969 3187
944 500 544
797 949 2069
872 998 1376
653 988 4355
381 819 6515
604 110 1488
884 869 5928
743 792 864
245 965 2435
299 458 5391
814 842 1398
317 132 460
42 789 1239
747 325 7838
577 713 1518
161 187 4371
241 817 3200
554 817 3343
129 448 5875
500 497 1080
737 359 3813
847 540 4782
98 323 6973
110 839 1860
142 717 456
333 282 1871
426 996 3361
612 880 6444
907 578 2429
121 914 1101
14 361 898
544 214 317
180 145 2431
120 636 3877
632 467 1698
15 288 4166
751 657 4552
574 113 1003
492 87 1974
111 182 7234
249 468 5766
173 431 4865
871 738 6098
969 825 7245
144 121 6011
773 570 3533
479 440 4601
931 681 5309
845 477 7989
489 445 7121
811 86 519
358 544 2843
197 731 3281
685 128 4037
233 94 5424
470 439 7732
514 3 4166
642 980 573
982 178 3131
625 136 2787
560 405 3249
73 676 2636
359 53 806
846 590 4721
488 324 972
658 166 6856
709 419 2633
287 344 8092
509 324 2086
337 416 5569
308 19 2107
582 304 5988
237 372 6803
224 97 2071
309 905 5735
172 14 7642
445 912 2768
929 527 366
735 461 6821
174 308 7449
539 817 3394
25 969 6763
247 699 4765
379 991 1267
39 172 4285
827 571 1101
112 365 5633
313 179 6803
859 813 6357
7 471 317
997 68 7093
797 309 6600
699 501 6492

2030633