title: Prims algorithm : Graph Theory
body: <p>Below is my Code for Prims algorithm, I am writing my own linked list as i have been asked to. It works fine for smaller number of vertices , but when vertices are large it fails.( I get 812800 as the answer for all large numbers as vertices).</p>
  
  <p>Input Format:</p>
  
  <p>First line has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.</p>
  
  <p>The next  lines each consist of three space separated integers   , where  and  denote the two nodes between which the undirected edge exists,  denotes the length of edge between the corresponding nodes.</p>
  
  <p>The last line has an integer , denoting the starting node.</p>
  
  <p>If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.</p>
  
  <p>Output Format:</p>
  
  <p>Print a single integer denoting the total weight of tree so obtained (sum of weight of edges).</p>
  
  <p>Sample Input 0</p>
  
  <pre><code>5 6
  1 2 3
  1 3 4
  4 2 6
  5 2 2
  2 3 5
  3 5 7
  1
  </code></pre>
  
  <p>Sample Output 0</p>
  
  <p>15</p>
  
  <p>My code passes the above test case , but fails the below one( I get 812800 for all large numbers).</p>
  
  <pre><code>1000 1000
  1 2 100
  2 3 200
  3 4 300
  4 5 400
  5 6 500
  6 7 600
  7 8 700
  8 9 800
  9 10 900
  10 11 1000
  11 12 1100
  12 13 1200
  13 14 1300
  14 15 1400
  15 16 1500
  16 17 1600
  17 18 1700
  18 19 1800
  19 20 1900
  20 21 2000
  21 22 2100
  22 23 2200
  23 24 2300
  24 25 2400
  25 26 2500
  26 27 2600
  27 28 2700
  28 29 2800
  29 30 2900
  30 31 3000
  31 32 3100
  32 33 3200
  33 34 3300
  34 35 3400
  35 36 3500
  36 37 3600
  37 38 3700
  38 39 3800
  39 40 3900
  40 41 4000
  41 42 4100
  42 43 4200
  43 44 4300
  44 45 4400
  45 46 4500
  46 47 4600
  47 48 4700
  48 49 4800
  49 50 4900
  50 51 5000
  51 52 5100
  52 53 5200
  53 54 5300
  54 55 5400
  55 56 5500
  56 57 5600
  57 58 5700
  58 59 5800
  59 60 5900
  60 61 6000
  61 62 6100
  62 63 6200
  63 64 6300
  64 65 6400
  65 66 6500
  66 67 6600
  67 68 6700
  68 69 6800
  69 70 6900
  70 71 7000
  71 72 7100
  72 73 7200
  73 74 7300
  74 75 7400
  75 76 7500
  76 77 7600
  77 78 7700
  78 79 7800
  79 80 7900
  80 81 8000
  81 82 8100
  82 83 8200
  83 84 8300
  84 85 8400
  85 86 8500
  86 87 8600
  87 88 8700
  88 89 8800
  89 90 8900
  90 91 9000
  91 92 9100
  92 93 9200
  93 94 9300
  94 95 9400
  95 96 9500
  96 97 9600
  97 98 9700
  98 99 9800
  99 100 9900
  100 101 10000
  101 102 10100
  102 103 10200
  103 104 10300
  104 105 10400
  105 106 10500
  106 107 10600
  107 108 10700
  108 109 10800
  109 110 10900
  110 111 11000
  111 112 11100
  112 113 11200
  113 114 11300
  114 115 11400
  115 116 11500
  116 117 11600
  117 118 11700
  118 119 11800
  119 120 11900
  120 121 12000
  121 122 12100
  122 123 12200
  123 124 12300
  124 125 12400
  125 126 12500
  126 127 12600
  127 128 12700
  128 129 12800
  129 130 12900
  130 131 13000
  131 132 13100
  132 133 13200
  133 134 13300
  134 135 13400
  135 136 13500
  136 137 13600
  137 138 13700
  138 139 13800
  139 140 13900
  140 141 14000
  141 142 14100
  142 143 14200
  143 144 14300
  144 145 14400
  145 146 14500
  146 147 14600
  147 148 14700
  148 149 14800
  149 150 14900
  150 151 15000
  151 152 15100
  152 153 15200
  153 154 15300
  154 155 15400
  155 156 15500
  156 157 15600
  157 158 15700
  158 159 15800
  159 160 15900
  160 161 16000
  161 162 16100
  162 163 16200
  163 164 16300
  164 165 16400
  165 166 16500
  166 167 16600
  167 168 16700
  168 169 16800
  169 170 16900
  170 171 17000
  171 172 17100
  172 173 17200
  173 174 17300
  174 175 17400
  175 176 17500
  176 177 17600
  177 178 17700
  178 179 17800
  179 180 17900
  180 181 18000
  181 182 18100
  182 183 18200
  183 184 18300
  184 185 18400
  185 186 18500
  186 187 18600
  187 188 18700
  188 189 18800
  189 190 18900
  190 191 19000
  191 192 19100
  192 193 19200
  193 194 19300
  194 195 19400
  195 196 19500
  196 197 19600
  197 198 19700
  198 199 19800
  199 200 19900
  200 201 20000
  201 202 20100
  202 203 20200
  203 204 20300
  204 205 20400
  205 206 20500
  206 207 20600
  207 208 20700
  208 209 20800
  209 210 20900
  210 211 21000
  211 212 21100
  212 213 21200
  213 214 21300
  214 215 21400
  215 216 21500
  216 217 21600
  217 218 21700
  218 219 21800
  219 220 21900
  220 221 22000
  221 222 22100
  222 223 22200
  223 224 22300
  224 225 22400
  225 226 22500
  226 227 22600
  227 228 22700
  228 229 22800
  229 230 22900
  230 231 23000
  231 232 23100
  232 233 23200
  233 234 23300
  234 235 23400
  235 236 23500
  236 237 23600
  237 238 23700
  238 239 23800
  239 240 23900
  240 241 24000
  241 242 24100
  242 243 24200
  243 244 24300
  244 245 24400
  245 246 24500
  246 247 24600
  247 248 24700
  248 249 24800
  249 250 24900
  250 251 25000
  251 252 25100
  252 253 25200
  253 254 25300
  254 255 25400
  255 256 25500
  256 257 25600
  257 258 25700
  258 259 25800
  259 260 25900
  260 261 26000
  261 262 26100
  262 263 26200
  263 264 26300
  264 265 26400
  265 266 26500
  266 267 26600
  267 268 26700
  268 269 26800
  269 270 26900
  270 271 27000
  271 272 27100
  272 273 27200
  273 274 27300
  274 275 27400
  275 276 27500
  276 277 27600
  277 278 27700
  278 279 27800
  279 280 27900
  280 281 28000
  281 282 28100
  282 283 28200
  283 284 28300
  284 285 28400
  285 286 28500
  286 287 28600
  287 288 28700
  288 289 28800
  289 290 28900
  290 291 29000
  291 292 29100
  292 293 29200
  293 294 29300
  294 295 29400
  295 296 29500
  296 297 29600
  297 298 29700
  298 299 29800
  299 300 29900
  300 301 30000
  301 302 30100
  302 303 30200
  303 304 30300
  304 305 30400
  305 306 30500
  306 307 30600
  307 308 30700
  308 309 30800
  309 310 30900
  310 311 31000
  311 312 31100
  312 313 31200
  313 314 31300
  314 315 31400
  315 316 31500
  316 317 31600
  317 318 31700
  318 319 31800
  319 320 31900
  320 321 32000
  321 322 32100
  322 323 32200
  323 324 32300
  324 325 32400
  325 326 32500
  326 327 32600
  327 328 32700
  328 329 32800
  329 330 32900
  330 331 33000
  331 332 33100
  332 333 33200
  333 334 33300
  334 335 33400
  335 336 33500
  336 337 33600
  337 338 33700
  338 339 33800
  339 340 33900
  340 341 34000
  341 342 34100
  342 343 34200
  343 344 34300
  344 345 34400
  345 346 34500
  346 347 34600
  347 348 34700
  348 349 34800
  349 350 34900
  350 351 35000
  351 352 35100
  352 353 35200
  353 354 35300
  354 355 35400
  355 356 35500
  356 357 35600
  357 358 35700
  358 359 35800
  359 360 35900
  360 361 36000
  361 362 36100
  362 363 36200
  363 364 36300
  364 365 36400
  365 366 36500
  366 367 36600
  367 368 36700
  368 369 36800
  369 370 36900
  370 371 37000
  371 372 37100
  372 373 37200
  373 374 37300
  374 375 37400
  375 376 37500
  376 377 37600
  377 378 37700
  378 379 37800
  379 380 37900
  380 381 38000
  381 382 38100
  382 383 38200
  383 384 38300
  384 385 38400
  385 386 38500
  386 387 38600
  387 388 38700
  388 389 38800
  389 390 38900
  390 391 39000
  391 392 39100
  392 393 39200
  393 394 39300
  394 395 39400
  395 396 39500
  396 397 39600
  397 398 39700
  398 399 39800
  399 400 39900
  400 401 40000
  401 402 40100
  402 403 40200
  403 404 40300
  404 405 40400
  405 406 40500
  406 407 40600
  407 408 40700
  408 409 40800
  409 410 40900
  410 411 41000
  411 412 41100
  412 413 41200
  413 414 41300
  414 415 41400
  415 416 41500
  416 417 41600
  417 418 41700
  418 419 41800
  419 420 41900
  420 421 42000
  421 422 42100
  422 423 42200
  423 424 42300
  424 425 42400
  425 426 42500
  426 427 42600
  427 428 42700
  428 429 42800
  429 430 42900
  430 431 43000
  431 432 43100
  432 433 43200
  433 434 43300
  434 435 43400
  435 436 43500
  436 437 43600
  437 438 43700
  438 439 43800
  439 440 43900
  440 441 44000
  441 442 44100
  442 443 44200
  443 444 44300
  444 445 44400
  445 446 44500
  446 447 44600
  447 448 44700
  448 449 44800
  449 450 44900
  450 451 45000
  451 452 45100
  452 453 45200
  453 454 45300
  454 455 45400
  455 456 45500
  456 457 45600
  457 458 45700
  458 459 45800
  459 460 45900
  460 461 46000
  461 462 46100
  462 463 46200
  463 464 46300
  464 465 46400
  465 466 46500
  466 467 46600
  467 468 46700
  468 469 46800
  469 470 46900
  470 471 47000
  471 472 47100
  472 473 47200
  473 474 47300
  474 475 47400
  475 476 47500
  476 477 47600
  477 478 47700
  478 479 47800
  479 480 47900
  480 481 48000
  481 482 48100
  482 483 48200
  483 484 48300
  484 485 48400
  485 486 48500
  486 487 48600
  487 488 48700
  488 489 48800
  489 490 48900
  490 491 49000
  491 492 49100
  492 493 49200
  493 494 49300
  494 495 49400
  495 496 49500
  496 497 49600
  497 498 49700
  498 499 49800
  499 500 49900
  500 501 50000
  501 502 50100
  502 503 50200
  503 504 50300
  504 505 50400
  505 506 50500
  506 507 50600
  507 508 50700
  508 509 50800
  509 510 50900
  510 511 51000
  511 512 51100
  512 513 51200
  513 514 51300
  514 515 51400
  515 516 51500
  516 517 51600
  517 518 51700
  518 519 51800
  519 520 51900
  520 521 52000
  521 522 52100
  522 523 52200
  523 524 52300
  524 525 52400
  525 526 52500
  526 527 52600
  527 528 52700
  528 529 52800
  529 530 52900
  530 531 53000
  531 532 53100
  532 533 53200
  533 534 53300
  534 535 53400
  535 536 53500
  536 537 53600
  537 538 53700
  538 539 53800
  539 540 53900
  540 541 54000
  541 542 54100
  542 543 54200
  543 544 54300
  544 545 54400
  545 546 54500
  546 547 54600
  547 548 54700
  548 549 54800
  549 550 54900
  550 551 55000
  551 552 55100
  552 553 55200
  553 554 55300
  554 555 55400
  555 556 55500
  556 557 55600
  557 558 55700
  558 559 55800
  559 560 55900
  560 561 56000
  561 562 56100
  562 563 56200
  563 564 56300
  564 565 56400
  565 566 56500
  566 567 56600
  567 568 56700
  568 569 56800
  569 570 56900
  570 571 57000
  571 572 57100
  572 573 57200
  573 574 57300
  574 575 57400
  575 576 57500
  576 577 57600
  577 578 57700
  578 579 57800
  579 580 57900
  580 581 58000
  581 582 58100
  582 583 58200
  583 584 58300
  584 585 58400
  585 586 58500
  586 587 58600
  587 588 58700
  588 589 58800
  589 590 58900
  590 591 59000
  591 592 59100
  592 593 59200
  593 594 59300
  594 595 59400
  595 596 59500
  596 597 59600
  597 598 59700
  598 599 59800
  599 600 59900
  600 601 60000
  601 602 60100
  602 603 60200
  603 604 60300
  604 605 60400
  605 606 60500
  606 607 60600
  607 608 60700
  608 609 60800
  609 610 60900
  610 611 61000
  611 612 61100
  612 613 61200
  613 614 61300
  614 615 61400
  615 616 61500
  616 617 61600
  617 618 61700
  618 619 61800
  619 620 61900
  620 621 62000
  621 622 62100
  622 623 62200
  623 624 62300
  624 625 62400
  625 626 62500
  626 627 62600
  627 628 62700
  628 629 62800
  629 630 62900
  630 631 63000
  631 632 63100
  632 633 63200
  633 634 63300
  634 635 63400
  635 636 63500
  636 637 63600
  637 638 63700
  638 639 63800
  639 640 63900
  640 641 64000
  641 642 64100
  642 643 64200
  643 644 64300
  644 645 64400
  645 646 64500
  646 647 64600
  647 648 64700
  648 649 64800
  649 650 64900
  650 651 65000
  651 652 65100
  652 653 65200
  653 654 65300
  654 655 65400
  655 656 65500
  656 657 65600
  657 658 65700
  658 659 65800
  659 660 65900
  660 661 66000
  661 662 66100
  662 663 66200
  663 664 66300
  664 665 66400
  665 666 66500
  666 667 66600
  667 668 66700
  668 669 66800
  669 670 66900
  670 671 67000
  671 672 67100
  672 673 67200
  673 674 67300
  674 675 67400
  675 676 67500
  676 677 67600
  677 678 67700
  678 679 67800
  679 680 67900
  680 681 68000
  681 682 68100
  682 683 68200
  683 684 68300
  684 685 68400
  685 686 68500
  686 687 68600
  687 688 68700
  688 689 68800
  689 690 68900
  690 691 69000
  691 692 69100
  692 693 69200
  693 694 69300
  694 695 69400
  695 696 69500
  696 697 69600
  697 698 69700
  698 699 69800
  699 700 69900
  700 701 70000
  701 702 70100
  702 703 70200
  703 704 70300
  704 705 70400
  705 706 70500
  706 707 70600
  707 708 70700
  708 709 70800
  709 710 70900
  710 711 71000
  711 712 71100
  712 713 71200
  713 714 71300
  714 715 71400
  715 716 71500
  716 717 71600
  717 718 71700
  718 719 71800
  719 720 71900
  720 721 72000
  721 722 72100
  722 723 72200
  723 724 72300
  724 725 72400
  725 726 72500
  726 727 72600
  727 728 72700
  728 729 72800
  729 730 72900
  730 731 73000
  731 732 73100
  732 733 73200
  733 734 73300
  734 735 73400
  735 736 73500
  736 737 73600
  737 738 73700
  738 739 73800
  739 740 73900
  740 741 74000
  741 742 74100
  742 743 74200
  743 744 74300
  744 745 74400
  745 746 74500
  746 747 74600
  747 748 74700
  748 749 74800
  749 750 74900
  750 751 75000
  751 752 75100
  752 753 75200
  753 754 75300
  754 755 75400
  755 756 75500
  756 757 75600
  757 758 75700
  758 759 75800
  759 760 75900
  760 761 76000
  761 762 76100
  762 763 76200
  763 764 76300
  764 765 76400
  765 766 76500
  766 767 76600
  767 768 76700
  768 769 76800
  769 770 76900
  770 771 77000
  771 772 77100
  772 773 77200
  773 774 77300
  774 775 77400
  775 776 77500
  776 777 77600
  777 778 77700
  778 779 77800
  779 780 77900
  780 781 78000
  781 782 78100
  782 783 78200
  783 784 78300
  784 785 78400
  785 786 78500
  786 787 78600
  787 788 78700
  788 789 78800
  789 790 78900
  790 791 79000
  791 792 79100
  792 793 79200
  793 794 79300
  794 795 79400
  795 796 79500
  796 797 79600
  797 798 79700
  798 799 79800
  799 800 79900
  800 801 80000
  801 802 80100
  802 803 80200
  803 804 80300
  804 805 80400
  805 806 80500
  806 807 80600
  807 808 80700
  808 809 80800
  809 810 80900
  810 811 81000
  811 812 81100
  812 813 81200
  813 814 81300
  814 815 81400
  815 816 81500
  816 817 81600
  817 818 81700
  818 819 81800
  819 820 81900
  820 821 82000
  821 822 82100
  822 823 82200
  823 824 82300
  824 825 82400
  825 826 82500
  826 827 82600
  827 828 82700
  828 829 82800
  829 830 82900
  830 831 83000
  831 832 83100
  832 833 83200
  833 834 83300
  834 835 83400
  835 836 83500
  836 837 83600
  837 838 83700
  838 839 83800
  839 840 83900
  840 841 84000
  841 842 84100
  842 843 84200
  843 844 84300
  844 845 84400
  845 846 84500
  846 847 84600
  847 848 84700
  848 849 84800
  849 850 84900
  850 851 85000
  851 852 85100
  852 853 85200
  853 854 85300
  854 855 85400
  855 856 85500
  856 857 85600
  857 858 85700
  858 859 85800
  859 860 85900
  860 861 86000
  861 862 86100
  862 863 86200
  863 864 86300
  864 865 86400
  865 866 86500
  866 867 86600
  867 868 86700
  868 869 86800
  869 870 86900
  870 871 87000
  871 872 87100
  872 873 87200
  873 874 87300
  874 875 87400
  875 876 87500
  876 877 87600
  877 878 87700
  878 879 87800
  879 880 87900
  880 881 88000
  881 882 88100
  882 883 88200
  883 884 88300
  884 885 88400
  885 886 88500
  886 887 88600
  887 888 88700
  888 889 88800
  889 890 88900
  890 891 89000
  891 892 89100
  892 893 89200
  893 894 89300
  894 895 89400
  895 896 89500
  896 897 89600
  897 898 89700
  898 899 89800
  899 900 89900
  900 901 90000
  901 902 90100
  902 903 90200
  903 904 90300
  904 905 90400
  905 906 90500
  906 907 90600
  907 908 90700
  908 909 90800
  909 910 90900
  910 911 91000
  911 912 91100
  912 913 91200
  913 914 91300
  914 915 91400
  915 916 91500
  916 917 91600
  917 918 91700
  918 919 91800
  919 920 91900
  920 921 92000
  921 922 92100
  922 923 92200
  923 924 92300
  924 925 92400
  925 926 92500
  926 927 92600
  927 928 92700
  928 929 92800
  929 930 92900
  930 931 93000
  931 932 93100
  932 933 93200
  933 934 93300
  934 935 93400
  935 936 93500
  936 937 93600
  937 938 93700
  938 939 93800
  939 940 93900
  940 941 94000
  941 942 94100
  942 943 94200
  943 944 94300
  944 945 94400
  945 946 94500
  946 947 94600
  947 948 94700
  948 949 94800
  949 950 94900
  950 951 95000
  951 952 95100
  952 953 95200
  953 954 95300
  954 955 95400
  955 956 95500
  956 957 95600
  957 958 95700
  958 959 95800
  959 960 95900
  960 961 96000
  961 962 96100
  962 963 96200
  963 964 96300
  964 965 96400
  965 966 96500
  966 967 96600
  967 968 96700
  968 969 96800
  969 970 96900
  970 971 97000
  971 972 97100
  972 973 97200
  973 974 97300
  974 975 97400
  975 976 97500
  976 977 97600
  977 978 97700
  978 979 97800
  979 980 97900
  980 981 98000
  981 982 98100
  982 983 98200
  983 984 98300
  984 985 98400
  985 986 98500
  986 987 98600
  987 988 98700
  988 989 98800
  989 990 98900
  990 991 99000
  991 992 99100
  992 993 99200
  993 994 99300
  994 995 99400
  995 996 99500
  996 997 99600
  997 998 99700
  998 999 99800
  999 1000 99900
  1000 1 100000
  337
  </code></pre>
  
  <p>Please tell me where I'm making a mistake.</p>
  
  <pre><code>import java.util.Scanner;
  
  public class Prim {
  
      public static void main(String args[]) {
  
  
     Scanner scanner = new Scanner(System.in);
  
     int N = scanner.nextInt();
     int m = scanner.nextInt();
  
     Graph g = new Graph(N);
  
     for(int i=0;i&lt;m;i++) {
  
         int u =scanner.nextInt() -1;
         int v =scanner.nextInt() -1;
         int w =scanner.nextInt();
  
  
        g.addEdge(u,v,w);   
      }
     int s = scanner.nextInt()-1;
  
     g.prim(s);
  }
  
  
  static class Graph{
  
   int V;
   static LinkedList adjacencyList[];
   static int key[] ;
   static LinkedList L;
   static Integer parent[];
  
    Graph(int v){
          V = v;
          adjacencyList = new LinkedList[v];
          key = new int[v];
          parent = new Integer[v];
          L = new LinkedList();
  
          for(int i=0;i&lt;v;i++) {
              adjacencyList[i] = new LinkedList();
              key[i] = Integer.MAX_VALUE;
              parent[i] = null;
              L.add(i);
          }
  
      }
  
      void addEdge(int u,int v, int w) {
          adjacencyList[u].add(v,w);
          adjacencyList[v].add(u,w);
      }
  
      long ans =0;
       void prim(int s) {
  
          key[s] = 0;
          while(L.head!=null){
          int u = getNodeMinkey();
          L.remove(u);
  
          if(parent[u] != null){
              Node n = adjacencyList[u].head;
              while(n!=null){
                  if( n.data == parent[u]){
                      ans+=n.weight;
                  }
                  n = n.next;
              }
          }
  
          Node n = adjacencyList[u].head;
  
          while(n!=null){
              int i = n.data;
              int w = n.weight;
              if(key[i] &gt; w){
                  key[i] = w;
                  parent[i] = u;
              }
              n = n.next;
           }
          }
  
          System.out.print(ans);
          //return A; 
      }
  
  
      static int getNodeMinkey(){
          Node n = L.head;
          int i = n.data; 
          int minkey = key[i];
  
          n= n.next;
  
          while(n != null) {
          if(minkey &gt; key[n.data] ){
              minkey =key[n.data];
              i = n.data;
          }
          n= n.next;
          }
  
          return i;
      }
  
  }
  
  static class LinkedList{
      Node head;
  
      void add(int d,int w) {
  
          if(head == null){
              head = new Node(d,w);
              return;
          }
  
          Node n = head;
          while(n!=null){
              if(n.next == null){
                  n.next = new Node(d,w);
                  return;
              }
              n= n.next;
          }
  
      }
  
      void add(int d) {
  
          if(head == null){
              head = new Node(d);
              return;
          }
  
          Node n = head;
          while(n!=null){
              if(n.next == null){
                  n.next = new Node(d);
                  return;
              }
              n= n.next;
          }
  
      }
  
      void remove(int a){
  
          if (head == null) {
              return;
          }
  
          if(head.data == a){
              head = head.next;
              return;
          }
  
          Node n = head;
          while(n.next != null) {
              if( n.next.data == a ) {
                n.next = n.next.next; 
                return;
              }
              n= n.next;
          }
  
      }
  
  }
  
  static class Node{
  
      Integer data;
      Integer weight;
      Node next;
  
      Node(int d){
          data = d;
          weight =0;
      }
  
      Node(int d,int w){
          data = d;
          weight = w;
      }
  }
  </code></pre>
  
  <p>}</p>