CT57877

Petr's Ledger of roads

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the obsidian flows of Blackglass with crates of roads, and Petr the dispatch writer must account for every last one. 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 <= 1019; 0 <= m <= 3057; 0 <= w <= 10.

Example 1:

Input: 857 1970 218 684 3 428 478 2 266 773 2 268 400 8 187 536 10 399 731 10 402 592 2 407 761 9 285 631 8 27 853 8 448 842 5 79 258 9 308 434 9 427 661 9 601 700 2 228 465 9 169 426 2 269 271 1 358 603 2 77 162 5 469 832 8 82 786 10 764 771 8 246 609 5 2 429 2 460 644 9 84 600 5 306 631 3 614 700 5 391 632 1 93 830 3 50 671 10 232 537 2 182 344 7 383 508 6 390 544 9 171 773 3 148 298 10 121 819 5 55 293 4 530 670 5 193 344 1 447 829 3 67 295 1 198 423 4 205 663 7 417 756 6 177 237 5 215 795 6 54 791 10 332 422 3 33 189 2 204 577 3 383 827 1 294 725 10 151 345 2 512 830 8 170 546 1 394 452 8 171 322 6 217 311 3 219 664 9 368 478 4 145 430 6 67 327 7 626 812 1 353 772 7 497 531 1 378 639 10 207 803 2 592 685 7 89 778 4 237 305 9 440 793 3 538 747 3 303 449 2 825 838 4 321 596 2 85 104 8 607 825 9…
Output: 2651

Example 2:

Input: 850 2979 262 353 1 17 412 4 585 752 4 104 736 1 406 424 2 1 720 5 180 522 2 342 442 7 454 567 2 339 456 4 383 756 8 350 636 7 155 595 8 13 336 4 81 535 8 321 334 7 65 167 5 180 338 7 85 94 8 475 478 8 315 834 8 543 704 9 416 696 10 140 765 10 563 679 10 558 710 8 45 507 8 519 661 7 240 794 2 62 745 2 70 742 6 87 450 5 5 805 2 4 652 7 247 293 1 319 370 10 440 593 1 155 382 9 162 791 1 146 163 7 18 60 6 14 491 10 178 195 6 411 626 1 545 751 9 363 740 2 105 551 9 32 574 9 58 187 8 98 722 4 270 651 5 338 638 2 550 818 4 338 611 9 358 438 3 325 491 5 440 485 1 302 405 6 303 476 8 297 719 4 358 367 2 343 621 4 583 777 2 54 271 6 519 733 2 141 481 6 538 651 8 143 694 8 203 355 1 194 684 3 514 634 6 89 348 4 388 567 9 546 717 9 347 644 2 483 811 2 332 613 2 388 588 7 559 796 2 126 395 3 231 345 6 …
Output: 1853

Example 3:

Input: 1000 2484 475 821 9 153 910 3 432 992 4 510 692 8 24 926 6 399 999 3 207 896 6 805 821 6 338 649 5 510 635 2 155 572 4 714 991 5 832 899 5 553 571 2 65 505 4 421 446 7 286 401 5 23 986 7 68 971 3 84 141 5 114 546 10 243 360 2 452 716 10 173 541 9 260 701 2 324 742 7 891 962 7 330 601 7 772 779 7 193 212 9 356 665 8 539 659 2 356 633 4 305 369 7 22 264 10 265 628 6 77 176 9 64 350 9 84 829 10 516 707 1 641 922 5 534 772 1 374 600 7 389 824 5 173 360 2 544 965 7 115 388 9 424 934 5 316 652 3 394 742 8 204 888 1 790 942 3 347 959 2 340 648 9 359 994 9 273 537 3 49 577 10 40 185 4 971 992 9 19 420 2 80 950 2 242 383 10 603 674 3 381 732 8 12 336 8 282 664 3 14 714 10 719 722 9 927 973 3 269 552 3 404 641 4 241 784 6 370 888 3 275 942 9 135 383 7 227 339 5 504 898 2 400 624 9 248 377 9 267 983 …
Output: 2910

Constraints:

1 <= n <= 1019; 0 <= m <= 3057; 0 <= w <= 10.

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