CT61224

Last routes of Tomas

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the wren hedges of Thimblewick opens only for a perfect tally of routes. Tomas means to find out. Task: Print the minimum total weight of a spanning tree, or -1 if the graph is not connected. Input format: First line: n and m. Next m lines: u v w. Output format: Print the MST weight or -1. Constraints: 1 <= n <= 1074; 0 <= m <= 3222; 0 <= w <= 1000000.

Example 1:

Input: 132 2654 1 70 869487 57 59 416181 17 132 844852 16 71 846757 109 128 561671 26 106 882019 3 116 412175 102 108 240751 77 85 842106 109 121 779429 63 106 374171 42 95 641249 86 105 59092 70 116 496636 56 79 326092 25 130 980695 54 68 563395 46 77 471707 66 99 673345 110 125 525317 46 125 555723 86 122 87453 48 70 33657 119 129 546857 79 105 265018 5 80 384336 75 115 4124 59 85 316001 15 111 73824 39 51 891875 55 59 365483 55 112 510589 31 119 729168 3 110 26473 23 73 727962 17 100 423046 6 91 914372 22 49 479700 15 55 796798 9 101 265031 27 87 200808 72 132 459495 51 52 929749 76 104 659407 76 116 787571 51 62 40406 52 81 929415 29 49 73322 67 97 982974 45 68 258036 8 55 268784 74 118 831632 22 28 956148 9 119 412301 46 92 502760 68 107 162801 73 100 866964 15 61 568311 117 131 932591 52 13…
Output: 3978750

Example 2:

Input: 223 2515 80 139 549922 88 143 52780 48 69 50954 42 90 349815 170 190 667040 68 130 666209 210 212 583251 31 119 538178 54 198 387019 52 175 593480 20 96 339227 88 91 268765 35 112 773082 8 41 817945 5 218 115915 131 193 690354 177 186 90819 125 137 512392 61 211 5576 192 216 927961 9 53 195466 21 113 419084 26 95 407941 61 76 803224 161 193 150040 140 218 709970 72 102 515937 105 212 77465 157 217 951331 133 176 443724 98 108 451133 85 105 983976 86 211 255680 126 187 872180 66 72 9797 42 195 876146 3 26 108347 118 156 640225 81 112 536768 55 167 835683 185 216 768069 155 165 818544 129 171 814001 8 150 399855 201 219 674949 102 222 973308 170 189 392235 71 82 458306 83 96 597461 111 195 904324 13 92 991288 46 119 495895 45 143 548141 86 222 128668 4 79 624218 105 194 467482 59 109 719378 …
Output: 11691187

Example 3:

Input: 707 3111 333 590 534296 152 320 104670 152 160 873865 496 499 788753 466 533 537835 449 485 871294 388 439 614308 229 340 830094 359 402 651558 110 443 943128 15 561 727473 495 641 753499 248 462 817057 450 655 192016 160 226 112710 254 665 892898 437 510 73715 202 399 923941 34 50 160911 471 584 981587 150 524 693534 235 593 215414 90 495 376581 78 576 667861 162 269 764385 44 442 15923 584 657 829107 78 362 858181 446 508 975825 21 500 655030 196 518 238955 170 549 254096 154 416 889327 574 706 918064 225 603 983144 95 621 436551 491 703 966203 120 362 66105 278 518 738638 73 409 213267 299 593 791282 198 645 913245 37 518 997021 117 435 100434 181 352 418576 109 217 677727 78 599 832676 65 380 830798 26 220 489665 161 331 757950 151 506 108062 485 579 361378 80 381 214291 75 540 776986 …
Output: 96395637

Constraints:

1 <= n <= 1074; 0 <= m <= 3222; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.