CT59929

The Marble Cable Plan

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Zephyr found an old ledger of bridges in the stall attic at the gull cliffs of Screech Point. The margin notes pose a precise question. 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 <= 830; 0 <= m <= 2490; 0 <= w <= 1000000.

Example 1:

Input: 760 1500 313 549 656185 159 390 773134 62 232 555509 79 129 73253 108 742 123870 498 643 443228 448 558 453461 55 77 192938 510 648 984457 304 493 418092 388 429 362087 356 637 263618 244 565 561766 740 757 281311 246 370 720168 71 329 631288 360 580 262386 471 756 291279 228 577 759020 7 312 580775 282 621 942590 1 559 454810 239 726 933110 168 528 22534 91 230 497095 125 191 77902 455 527 912564 260 562 202817 152 755 343728 216 217 652030 393 459 297035 56 227 193792 36 475 744184 66 297 6132 65 247 642973 315 613 833687 111 344 501645 386 644 345339 580 680 103890 42 604 416134 28 188 489449 263 671 328942 529 560 702728 266 440 934969 238 404 779913 444 682 845120 124 539 644282 399 424 436649 510 625 639451 350 555 971226 177 708 895125 91 421 262866 324 343 720345 192 347 411647 335…
Output: 217303756

Example 2:

Input: 394 1674 49 272 184124 7 166 956449 21 379 380280 122 195 555404 190 293 830028 158 274 394864 13 145 879407 109 144 391293 53 267 980559 91 218 354442 14 106 737186 116 257 511323 55 129 327038 178 321 282398 8 102 222719 207 240 125118 48 362 758323 364 376 698888 117 122 78508 5 178 866797 279 284 580526 29 336 67189 81 385 594814 73 181 939357 338 378 940913 106 380 765250 279 311 114197 83 217 78944 267 270 540066 142 155 108833 322 386 922984 272 276 292295 26 292 427822 151 175 254451 63 216 642041 147 181 925433 292 359 849131 10 28 394159 127 348 424575 86 361 172034 166 256 137239 20 235 443356 351 377 236732 230 257 889483 30 52 531743 128 342 4757 102 234 328276 46 56 115249 154 273 110535 95 275 984505 86 212 432471 120 272 957807 16 65 171546 62 236 917369 42 167 118964 54 72…
Output: 52573890

Example 3:

Input: 556 1579 527 530 68868 321 425 584611 238 490 693945 293 542 283044 34 267 78684 75 329 659456 149 196 867040 67 368 857964 159 271 152311 218 276 645754 374 477 666555 101 364 453601 77 81 524746 223 449 83201 278 436 30632 442 528 440897 224 323 468205 488 520 83984 164 509 654651 237 265 698283 263 470 449221 73 194 829054 156 261 456173 177 389 131351 72 508 36270 118 153 270368 86 323 595961 101 300 981203 292 305 667428 322 449 731723 256 500 717854 75 171 894971 315 492 788338 233 381 275352 195 265 341239 65 539 541858 50 115 633494 293 371 12218 59 532 631678 160 291 977397 206 449 916134 100 166 913456 321 422 752301 230 438 426843 1 277 640375 31 259 387466 199 337 45697 105 135 536427 42 222 417603 437 461 653404 360 492 833641 344 362 963107 425 476 849450 155 338 902079 167 4…
Output: -1

Constraints:

1 <= n <= 830; 0 <= m <= 2490; 0 <= w <= 1000000.

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