CT61425

The Sterling roads of Rekha

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the obsidian flows of Blackglass opens only for a perfect tally of roads. Rekha 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 <= 1461; 0 <= m <= 4383; 0 <= w <= 1000.

Example 1:

Input: 1438 3661 126 755 842 114 705 891 424 854 670 457 985 345 792 888 596 251 722 630 2 191 328 538 882 570 89 140 946 185 365 349 408 637 976 893 1184 502 288 747 247 820 1070 876 338 586 26 112 1214 611 381 617 971 506 1380 693 617 1265 848 1264 1357 166 25 1421 794 113 1350 433 387 1122 596 18 956 670 838 994 378 318 1424 986 306 1358 26 309 1189 816 101 1169 232 60 256 151 884 974 624 890 1221 646 770 1230 610 618 1033 866 111 159 747 260 1370 188 196 327 294 422 1217 997 834 1028 486 1004 1081 838 320 959 979 344 450 8 180 576 411 153 1048 630 370 1029 521 555 761 656 263 1392 518 793 915 470 406 624 497 811 1048 506 140 637 625 494 1221 525 249 283 366 99 1418 328 843 1017 993 144 228 891 356 1317 557 393 1081 936 793 1296 732 324 1175 939 180 434 804 197 292 79 240 1028 36 576 988 463 9…
Output: 326806

Example 2:

Input: 1413 2465 101 1085 338 332 411 7 540 546 265 996 1329 473 38 394 252 683 1303 606 459 827 768 668 677 455 222 1298 526 413 1022 743 741 972 780 281 759 159 903 947 80 1291 1385 52 348 1145 109 900 1123 324 394 798 514 901 1386 978 433 1217 715 711 801 454 705 1188 498 307 1310 950 888 1294 742 34 703 884 497 539 612 753 1351 73 738 1059 767 271 761 976 925 1205 352 810 1248 188 24 973 468 301 1249 837 623 711 313 238 935 864 115 789 552 275 798 165 82 755 707 367 712 760 186 1058 131 665 1032 199 939 1410 270 839 926 781 704 804 354 339 455 158 661 1286 749 164 216 511 914 948 211 372 1099 402 1006 1262 328 1262 1349 871 738 874 462 418 1242 972 431 1001 189 449 1166 62 857 1381 854 572 823 759 657 1098 586 323 1150 809 257 1139 195 1124 1157 554 788 1257 483 1104 1347 481 474 476 899 278 …
Output: 440518

Example 3:

Input: 1453 4234 619 1250 426 311 453 296 1112 1161 407 368 796 471 671 697 856 20 885 171 472 653 296 617 671 812 1189 1393 810 1318 1410 719 416 1201 789 372 910 802 486 1407 131 512 1317 808 636 1410 943 28 1146 702 498 1178 290 392 983 168 269 1228 683 282 1088 758 1097 1200 170 897 943 501 720 920 883 229 999 45 40 316 624 100 736 226 733 821 416 565 1100 834 1173 1177 50 867 872 618 702 961 349 1003 1404 953 634 935 807 350 1316 606 152 1302 686 374 544 123 245 1108 508 448 862 87 1353 1362 820 323 771 124 665 1359 11 153 1439 246 43 937 805 863 1191 792 177 541 848 494 939 746 899 910 188 1080 1346 882 10 1059 937 79 977 125 182 1379 878 293 903 936 1 527 141 246 428 490 343 1028 763 1092 1181 453 237 897 79 1049 1405 919 541 1418 324 828 1226 327 226 480 582 307 1110 596 300 1145 417 315 …
Output: 291705

Constraints:

1 <= n <= 1461; 0 <= m <= 4383; 0 <= w <= 1000.

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