CT65046

Last corridors of Mason

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the quays of Driftwood. Mason spreads the corridors records across the table and picks up a sharp pencil. 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 <= 1138; 0 <= m <= 3414; 0 <= w <= 1000000.

Example 1:

Input: 699 891 153 300 705395 232 450 275304 98 265 328405 404 458 102436 146 571 814760 83 522 981457 375 679 356821 51 449 607059 297 591 224840 158 660 443303 84 584 388602 367 591 2899 463 502 867600 133 649 561186 251 315 153664 404 494 764531 74 285 909216 322 682 948743 132 674 203809 111 659 907675 246 439 741748 107 304 970425 277 536 308703 126 675 564985 192 352 625166 62 252 513351 417 638 777948 11 34 305809 20 246 491346 220 578 38848 118 376 741151 121 245 602365 206 471 304062 216 491 256948 39 666 714959 391 503 390435 129 228 902363 175 310 906874 98 520 639859 9 494 106993 56 327 7431 280 628 648626 71 543 309108 318 442 727928 541 542 547858 606 610 151094 12 250 741832 195 375 876072 316 466 819604 104 181 65942 233 559 501721 167 546 489066 415 459 748461 63 355 378192 331 5…
Output: 284063598

Example 2:

Input: 723 1988 93 310 979526 21 255 59668 177 625 636793 305 584 451396 327 542 872744 59 640 648534 186 307 997725 551 651 796487 33 435 486787 113 516 967481 156 538 464837 502 577 579266 42 210 419294 71 474 450345 9 668 985084 60 170 365890 417 534 586411 84 515 94993 379 530 917063 218 439 815067 241 292 130735 344 515 434923 246 582 470822 313 580 224915 28 296 787115 427 526 649316 199 539 222370 486 605 705141 505 593 469860 32 346 993417 193 284 639276 156 376 670076 413 550 710690 112 543 256050 122 193 684496 275 330 455322 243 345 998645 463 687 551560 406 446 695548 209 219 351344 399 422 843061 209 678 625868 70 685 897225 355 555 954037 404 532 403548 75 227 462728 108 283 375680 141 290 160403 152 287 954345 9 293 876060 142 668 931989 317 380 822904 208 291 3236 205 484 525954 3…
Output: 160421806

Example 3:

Input: 751 3281 542 720 41530 468 619 310313 482 590 784384 284 480 853558 444 565 577465 245 635 273040 263 307 367843 351 733 225724 279 736 866331 145 186 96327 522 645 871897 3 378 776449 222 668 240673 289 395 154182 182 694 608014 194 566 80752 480 654 654865 71 541 624129 339 669 40919 255 620 387344 439 714 181338 460 475 379068 86 499 291007 149 247 422940 124 190 775973 114 456 150394 183 419 343198 13 30 167907 50 477 860755 125 321 304957 306 385 27483 446 527 543095 176 411 748270 46 86 921033 71 564 60019 575 691 437073 359 375 787709 133 381 96263 207 311 22503 266 703 469428 139 584 395426 302 694 879768 426 491 804733 493 593 529591 332 509 215513 228 715 491189 250 484 99614 205 688 595346 603 613 433026 226 317 239956 147 551 452942 500 658 837298 291 722 304744 477 519 249425 …
Output: 101487009

Constraints:

1 <= n <= 1138; 0 <= m <= 3414; 0 <= w <= 1000000.

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