P19542 [HackerEarth] The city Manyonok has N substations . The substation numbered 1 houses the mayor Alisa. Each substation has a chief who is in charge of the functioning of that particular substation. Du
普及-
题目描述

The city Manyonok has N substations . The substation numbered 1 houses the mayor Alisa. Each substation has a chief who is in charge of the functioning of that particular substation. Due to an emergency the Alisa has decided to call all her chiefs to substation number 1.

There are M roads forming a road network between the N substations . Initially all the roads are closed . The cost of opening the road joining u and v is denoted by c(u,v) . The mayor Alisa has to bear this cost.

Alisa's city Manyonok , like many other cities are running a bit of a debt . As a result she wants you to find out the minimum cost incurred by her for all the chiefs from substations 2 to N to come to substation number 1.

Constraints
1 ≤ N ≤ 100000
1 ≤ M ≤ 100000
1 ≤ u,v ≤ N
1 ≤ c(u,v) ≤ 10^9

Input
The first line contains the integers N and M.
The next M lines are of the form : u v c(u,v)
It is guaranteed that the graph has no self-loops,multiple edges and is connected.

Output
Print a single integer - the minimum cost incurred by Alisa so that all the chiefs can come to substation number 1.

SAMPLE INPUT
4 5
1 2 2
1 3 3
2 3 1
2 4 7
3 4 6

SAMPLE OUTPUT
9

Explanation

The roads joining 1-2 , 2-3 , and 3-4 can be opened so that chiefs in cities 2 , 3 and 4 can come to city number 1 . The cost incurred is 9 .

输入格式

见题面

输出格式

见题面

样例输入
55 1000 30 1 783153880 37 2 776850051 42 3 985109226 19 4 851184314 45 5 178727300 31 6 117550813 34 7 102832768 36 8 515296974 37 9 412052420 31 10 910737077 6 11 977995693 21 12 903821334 19 13 589084986 23 14 414122453 10 15 803509779 6 16 322787304 38 17 304357100 33 18 87256617 32 19 824222307 5 20 729397487 45 21 123986602 2 22 938955231 33 23 778000547 18 24 136246156 40 25 742525144 30 26 214753586 6 27 593484777 21 28 110255025 10 29 219736449 31 30 624153866 32 31 651520075 33 32 504614885 15 34 222568796 36 35 581076956 2 36 225374973 6 37 891556802 30 38 30262400 46 39 575695934 38 40 70827787 17 41 894312498 9 42 908721287 32 43 350216579 34 44 699683534 32 45 583058601 36 46 55291535 18 47 78748115 40 48 96219844 15 49 613309406 49 50 979276378 32 51 919867734 32 52 435861652 37 53 580311863 44 54 524102891 45 55 343747667 13 37 929010529 53 8 13824931 19 2 423636492 48 24 125592881 16 49 746371185 41 22 966416960 26 55 506148466 32 17 385630867 6 43 384562808 10 1 33711124 49 19 518222010 20 22 673055295 37 36 63179544 24 49 771245708 30 7 618091196 8 27 897925102 25 52 738576227 52 7 147637433 55 36 93913870 34 52 807512127 11 33 936017120 18 40 624948943 46 7 357060992 16 39 448921851 27 52 67360768 40 41 947558222 11 26 904042299 21 2 188037635 4 22 10046695 12 39 447405860 48 37 394650608 51 30 859026289 45 20 16353762 37 25 320084845 20 16 479275010 46 55 800896502 31 50 666635619 42 15 530154851 11 4 453188372 41 7 164449908 34 8 497780141 25 36 141830396 28 41 491448084 15 29 656618346 54 8 205309776 23 47 852482490 22 21 658012125 30 5 740780885 49 45 536107179 47 41 62103619 6 25 837278795 14 46 293433831 6 34 527942791 53 27 313966317 28 15 39680321 39 51 54042544 3 55 224078772 55 10 263348895 2 32 36306828 28 33 925342589 41 8 163643483 48 52 405111381 46 48 238838465 9 1 51858302 38 36 458999941 54 42 772502745 11 29 660007119 9 15 179555325 37 43 675139983 21 16 914934518 1 44 899203815 38 3 241129204 52 31 387895883 53 16 326826768 24 45 495621494 22 23 250589083 47 39 585999134 21 53 244273010 55 13 375972436 37 31 275332894 1 5 944666340 36 17 803517280 1 16 786556463 27 41 692027495 38 11 360018827 55 23 263202295 23 16 693521431 45 28 935406420 26 6 736145805 4 46 903700187 8 5 510850216 46 18 617454311 9 33 289022746 27 1 207579717 15 50 133882755 4 5 90573451 13 44 454406966 39 49 435732801 34 36 635643212 38 54 687347481 15 2 326145459 35 51 239772169 20 23 582519397 36 45 392593976 52 18 633544067 10 9 67087426 24 27 188777597 22 49 219865013 49 14 661974360 51 19 224093656 8 49 682394268 14 18 380363915 45 19 301331786 23 25 835456311 13 51 762969149 5 41 993195807 22 42 951998064 4 35 17666868 8 6 380960210 46 47 841329100 16 3 565332126 9 46 808990094 53 25 663237225 14 7 422160363 28 18 887114637 35 26 85343901 17 12 417152476 29 35 539086210 27 30 369282598 15 48 132904902 48 17 192312923 38 47 505372756 52 19 251380451 38 51 700625489 17 33 35655513 28 8 212452169 34 42 975478889 43 54 934896832 25 22 515705949 15 25 224614081 28 30 685790176 16 12 700948554 10 20 536466963 42 13 373906991 54 5 197209295 8 9 379659031 19 41 899672771 36 33 718797663 54 11 912604577 36 12 716463573 12 31 815019623 10 7 811411169 6 39 320100861 35 13 99900492 29 20 480664342 50 35 724585599 1 29 906413492 50 32 57797531 11 22 606356252 6 9 957186269 44 4 10704797 25 49 162412502 53 45 515980255 51 29 327486790 52 39 280985115 19 54 444489293 45 52 527214418 36 4 913317900 54 37 24561277 9 17 272137260 29 14 38954935 39 18 64328115 23 12 640355091 55 31 154017409 50 1 100705696 8 16 24130096 32 12 39325831 39 24 198642342 2 27 733226390 15 26 867420062 52 12 434865848 29 3 242528423 13 18 105095619 8 4 592178970 27 17 124665111 6 41 596524489 23 15 318401921 30 42 12097923 34 9 476585034 31 29 142711480 38 6 711320606 50 54 240448727 55 39 654845182 14 13 910750478 6 33 70302606 51 34 555616552 47 40 571545631 37 10 435160125 9 2 224169493 32 18 845276117 46 23 178438945 38 32 986879759 35 1 408506575 11 36 727740872 34 27 686347340 7 33 818690560 54 31 966634388 49 34 199508046 12 41 585806305 45 26 569055841 30 41 77023247 5 35 817647512 54 9 32023271 5 17 903725353 3 5 447306671 52 5 11843420 4 24 936737117 5 37 901425883 38 26 999159409 31 49 135424793 45 14 34250841 4 12 87258756 12 53 239187927 7 6 431561713 13 26 95944690 44 32 93866994 20 30 11549727 36 18 306028143 23 36 784275895 40 53 165021526 28 24 473702260 45 12 358473917 40 2 212827526 7 4 83625638 55 19 859898750 45 30 130599063 43 13 315638040 43 12 713478464 35 54 254982728 35 31 558346788 21 9 285453742 9 29 589089643 55 27 104559414 41 20 876697393 13 45 977111794 29 41 393927511 17 43 674799100 42 26 13113029 36 43 100755725 54 24 336480031 13 40 744532639 47 2 711959512 26 19 296819154 29 8 765699389 12 38 193226914 32 9 815874318 45 16 695840892 8 31 443689917 16 38 501626356 10 36 505232726 28 42 845778145 35 27 404931623 22 31 354343264 4 25 434627255 49 1 764538323 51 5 429144924 44 53 945971773 8 38 654850199 52 51 783362637 14 15 494139076 16 47 846228725 16 48 556410720 26 43 107813373 41 25 735678811 32 23 215302874 20 33 106024105 12 3 100012798 12 1 953360345 51 37 996225249 42 10 566321360 13 11 20680759 9 4 805935329 35 24 932652110 12 26 651441445 53 43 17517928 34 46 433352564 4 20 281538785 6 28 887222718 44 28 853964301 42 24 417482027 18 48 40432169 10 30 197011946 4 37 577090610 35 44 197980665 9 35 297408989 6 32 591389843 27 36 113199720 48 22 52540769 44 55 164684611 26 1 596906852 25 27 441138953 2 41 77751228 9 31 226392034 22 12 688582593 28 36 108183459 55 47 421693021 30 43 976376997 7 29 220462768 11 12 722308738 2 25 777705973 37 39 162042443 22 46 962065694 54 22 852108012 22 52 69651391 43 7 945825415 6 46 882669417 48 32 203168756 39 40 232348417 11 34 68232508 19 31 424464586 46 28 443759792 10 52 810930534 21 17 82781621 35 40 508567556 7 21 178390121 39 9 670319832 41 53 903395023 39 1 126924768 49 6 794887596 27 19 363935621 51 33 351803293 16 17 420062570 39 13 90691175 10 34 258262470 45 10 448897539 49 12 662576476 39 26 155984045 7 55 134240647 9 38 250768406 2 31 430249406 8 17 650016411 3 13 49128354 13 41 428010221 36 21 276039095 52 41 209983128 15 1 744605028 44 15 309594956 16 41 646883689 55 42 284367275 36 7 173739979 20 50 415261199 9 5 798119753 28 47 137155827 4 32 9304270 45 9 358132086 38 25 572631697 23 42 745739960 18 50 118409693 11 47 536041099 4 17 845138284 35 33 83525763 21 48 104800790 26 37 986621044 48 36 197127530 15 24 486977239 44 22 422782161 13 27 232822947 26 20 131461611 9 53 959987201 55 4 297577679 30 14 920326423 42 20 624900964 1 14 927941076 38 41 151108766 47 43 815952184 46 17 637188560 52 50 35445593 15 3 611741423 1 55 676589254 19 50 120118576 47 24 765311385 52 6 142467902 4 49 593171979 20 46 13750004 48 29 670648337 25 31 62335160 52 23 260309178 37 29 953946871 54 34 637536219 9 11 675539952 25 35 921787157 50 43 894127360 51 48 16708618 14 35 175958203 19 18 587134256 24 41 172607210 26 41 995452163 39 54 455183095 13 47 539675943 2 34 462000015 2 11 190263303 40 29 851758265 29 50 39500155 5 42 954656991 37 32 970162890 19 14 999858195 15 37 491771885 37 23 597845610 25 44 50409417 6 24 297455752 48 45 936654930 30 19 922138751 10 38 899399990 20 40 100353693 8 2 515957304 36 14 771692041 16 52 250894919 12 33 844212866 10 3 184266895 50 23 916039422 21 3 783294941 30 50 888793257 50 51 972453013 48 30 163128146 20 31 501817826 23 17 283385087 11 32 743584926 32 10 894081639 47 10 666137901 18 55 422215181 24 55 108178252 19 28 892234176 11 25 36223183 55 32 696915892 41 45 999884989 45 25 963972655 48 54 109936278 9 55 447799997 22 50 685359320 11 7 296872377 5 53 610356003 24 46 115924279 4 16 884969258 27 9 374099819 16 37 29637896 49 20 677227209 49 51 272955657 39 25 387755438 16 30 342263038 13 21 142055415 22 18 780515757 47 50 875969179 12 37 580613059 3 28 901144883 53 23 544177791 16 40 92408959 11 3 12446166 53 48 822761123 42 48 519764898 7 42 812779288 48 34 827248007 5 38 3881847 25 33 12165354 26 4 888504008 54 55 548879750 38 14 406671533 19 43 866819417 52 3 829127046 26 7 21042949 27 45 126396382 39 38 190577626 22 40 442510600 46 41 648453563 28 54 260442850 2 44 907449155 38 33 660935232 29 26 6343199 29 2 90130120 18 10 466474345 41 42 535237046 54 10 641512739 14 33 532325254 21 50 885570841 44 47 345221400 26 24 687698837 28 26 482996787 27 23 999794944 26 21 427285591 48 27 612503797 42 36 383216214 53 33 864905459 30 24 231383187 44 8 846961773 12 27 941839741 34 18 209468869 18 23 331934017 15 12 843240295 4 41 224627880 23 48 537823240 16 15 234274002 51 42 789512176 20 14 470287212 40 31 266694344 54 33 708423911 44 42 225076746 6 55 941555213 14 5 849392268 3 41 148414794 25 43 981351848 31 34 66501179 21 51 981508112 36 49 94190257 51 1 716043118 49 18 350164628 16 36 654131733 20 44 843254995 6 40 171323901 8 47 639567118 46 26 684454923 36 47 761012091 41 31 365268922 23 2 434308185 37 3 498671077 10 17 361238114 43 23 254022646 43 5 134039485 53 13 648439368 31 4 898871210 20 25 620194456 26 10 855236717 3 7 13233 48 20 707574514 41 34 390339035 5 19 374114120 8 46 375394528 5 49 439412058 28 27 339550035 25 47 995431447 9 25 363153456 16 9 246909013 27 5 679868619 51 18 433654418 3 20 281240389 55 15 13609616 8 11 921039158 10 50 979808573 26 50 195861817 46 33 64391917 49 42 897346804 3 36 944638974 26 32 637921460 52 29 23278841 50 2 925020719 40 37 993372905 22 33 603255773 24 2 23243125 20 8 490459623 13 24 566231178 24 17 425035252 28 5 404185742 25 30 430354716 51 43 81872956 18 11 686169684 48 1 655380888 2 33 22252160 55 16 93380188 4 43 192788373 13 1 336591021 41 44 69887792 27 22 154530772 9 36 597944681 19 48 279014847 20 47 163465381 20 39 705512359 53 42 554003106 20 51 109183376 45 23 12169852 26 27 704965548 7 12 42699049 7 28 518600831 3 47 641263275 30 47 410921789 51 17 473583164 34 4 137595368 44 16 857568340 17 45 785679075 2 45 449174762 15 36 135928221 50 17 506381735 8 55 40131397 13 4 688309157 14 22 333439262 2 13 461036925 21 33 127421 42 11 892377259 5 22 708574414 23 41 857422403 42 12 226046983 8 3 148824431 7 22 844997460 17 30 883265715 18 5 953144909 24 43 820380110 37 41 629943540 23 31 969373237 47 48 229650901 38 52 409335810 10 14 545771271 17 26 99036915 5 11 881209187 54 1 286106758 50 33 76286190 46 30 565505280 42 32 544181657 8 43 551664371 26 33 636714856 5 33 760859789 53 3 30027750 39 44 968576068 28 40 687417548 40 7 103464503 45 42 18732017 45 1 618672824 22 53 875828260 38 29 829180377 15 43 122631983 26 54 397746856 25 26 972493811 53 55 391518224 34 30 828138739 3 18 371586090 36 39 622048972 2 30 84760836 44 38 8141053 6 3 435893844 8 40 894838374 46 42 624528524 43 3 765132254 16 27 957758208 21 42 355703049 46 2 729118534 8 33 610048744 24 31 46599496 46 5 735637173 13 16 372366486 10 51 390491508 7 25 74315377 30 37 386660896 45 46 197989577 10 11 100117331 32 49 278694405 43 49 108748852 24 19 150868622 54 45 705085999 8 22 910518587 45 40 388512317 16 24 63486971 27 51 249069393 34 13 295911559 34 19 141893683 13 30 132278683 31 48 612030493 3 39 972717732 40 12 229326867 1 32 68366428 11 37 980684037 17 25 824551708 51 36 771185326 50 16 662334677 25 42 685584521 40 9 587790046 42 33 310863812 29 19 647471116 19 9 31695223 42 6 603614310 28 37 530274510 43 33 18699630 45 50 764132695 35 41 406907550 3 50 53903443 17 53 330935723 12 5 273310666 35 45 139143654 30 9 349123593 31 46 51624408 44 3 424572100 11 31 93196064 10 5 490379973 32 54 610832877 48 44 974811170 10 49 16515095 1 7 521352508 7 27 542429441 10 12 648764861 12 13 21781926 40 24 779544462 55 21 544172423 11 46 960821548 3 4 216439421 13 9 141444028 31 38 507546445 40 10 816199617 32 14 322485856 27 38 227886110 15 5 890464352 21 4 901036649 43 55 282274844 39 5 536762270 7 53 138607952 40 11 150698815 15 54 549212528 4 33 718366261 9 43 79980588 40 1 656036072 4 6 341247870 42 29 374723997 28 39 42333167 1 8 907260795 6 20 261968785 45 29 402002484 28 48 256158060 9 22 80006118 1 6 738765109 29 21 323457435 11 48 740857171 26 2 704226978 36 41 926750482 46 29 971903965 55 35 961427337 21 5 797370703 49 55 393415545 36 54 810252183 19 10 695616955 15 11 135514124 17 20 5415509 20 55 509704030 52 24 685493582 25 24 587889963 34 39 635570491 52 36 517320390 32 35 414320115 50 13 303828441 36 22 25136164 51 25 677018813 14 37 34606794 17 52 939257475 50 37 923978564 42 40 226154193 13 33 374111462 37 42 156711213 25 12 316351744 52 28 606854757 20 13 230288786 14 8 195978286 17 42 203166818 47 53 211612044 10 33 706958290 31 7 323276493 55 40 442415714 38 50 120571338 18 2 940031728 8 45 476702376 41 55 99911173 52 43 369576810 2 52 155615756 11 14 442884209 38 35 129014602 9 49 75593779 36 44 560621006 52 37 297336023 20 38 555073718 25 32 995870926 36 32 490378733 19 39 19294179 45 39 630924452 1 37 62796764 16 19 740762831 12 46 146769382 55 30 770689282 52 40 450536089 29 25 617344617 3 22 16673967 55 11 31500114 37 49 529259005 47 1 50193948 48 13 379434028 3 14 224112179 50 12 73992133 15 52 175637400 36 24 61913342 6 35 685811068 37 45 698970549 12 35 717498864 28 2 819001428 52 49 713099119 8 23 667684834 43 18 140831277 35 7 127610351 8 50 788880599 40 46 18281501 39 43 46386958 35 39 872352095 2 49 319014423 38 48 857214972 51 45 186912260 54 49 389466824 24 33 20383330 3 1 838439701 49 46 56361590 32 39 646599034 12 2 353389396 14 27 450901369 6 47 577777504 7 37 211793824 23 40 414846962 54 53 892140941 27 47 814343048 49 33 118389217 27 42 994701814 47 33 905204016 40 14 177041800 17 28 939635856 1 19 280597974 10 16 706872660 54 2 292244297 51 16 365757937 13 25 134741663 2 16 645382260 21 30 336182464 18 42 408155781 38 45 135395852 29 27 505939151 15 7 994225783 25 19 296367034 27 4 75374115 44 46 907932154 30 3 266419118 44 7 965301554 22 51 478630460 6 17 637747444 36 31 504682365 42 47 298665572 16 14 40837444 19 35 248652960 48 41 741426191 52 33 420259434 30 54 136295707 17 44 781252152 18 45 478917568 11 16 627815583 48 2 414956966 20 12 305358133 8 7 602612576 28 20 307010698 12 8 212282287 31 5 536642878 55 5 807511901 26 16 631131764 43 34 889247705 41 9 506436488 1 52 554710517 10 53 484145031 27 33 154429989 20 15 639130444 5 25 579977043 21 14 464333471 44 12 182401419 19 33 269201488 3 33 277615602 17 40 237889176 43 14 84483172 15 41 846818554 19 15 960827557 49 17 8953563 51 47 34804392 48 35 70391573 14 54 611611544 22 43 244779724 49 21 528337298 15 17 768342602 31 3 767077781 6 23 704487012 34 55 910155193 47 7 167106942 31 33 565521995 4 54 435907206 47 22 41644572 14 42 5730431 19 22 161220909 24 7 255095342 55 50 59586367 50 42 956572655 32 24 13891674 54 41 286869600 48 3 656515512 39 8 883061270 8 10 449037720 34 12 498161070 9 50 540860686 24 3 12516670 11 30 491966992 38 18 155566716 21 38 485824050 27 49 693407592 25 55 420269940 22 24 65725335 6 12 910403583 46 38 638507277 38 4 142324460 34 3 475583773 26 9 623846794 31 44 75707451 29 53 59444497 43 45 879666278 36 20 142887823 46 53 492943651 30 8 793957844 47 5 86935349 3 49 38702679 50 41 732122756 1 24 619230189 29 55 901930117 50 28 643805634 8 48 600505737 50 44 801351044 43 2 585887876 4 1 74782588 15 53 686259185 28 23 319362000 34 23 278851910 38 42 58667577 5 44 612441045 24 51 609468535 51 31 918882850 49 11 663083114 23 49 473252394 5 40 167326413 34 26 974565805 20 34 227083122 6 5 386387661 29 39 154531753 16 25 108314916 35 34 732848051 19 36 59402643 16 29 525204348 32 40 259873336
样例输出
152812804