{+--------------------------------------------------------------------------+}
{|        The Textbook in Data Structure, Algorithms and Programming        |}
{|              http://w...content-available-to-author-only...c.jp/~hoangle/DSAPTextbook/               |}
{|                                                                          |}
{|    Program: Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm    |}
{|                         Written by Le Minh Hoang                         |}
{|                      Email: dsaptextbook@gmail.com                       |}
{+--------------------------------------------------------------------------+}
 
{$MODE DELPHI} (*This program uses 32-bit Integer [-2^31 .. 2^31 - 1]*)
program Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm;
(*
IMPORTANT NOTES FOR COMPATIBILITY:
==================================
- This program is especially written for running under Windows 32 bit and
  Free Pascal IDE. Therefore, 32-bit Integer type is used to result in the
  best performance with the {$MODE DELPHI} compiler directive of FPK for
  Windows.
- If you use Borland Turbo Pascal 7 for DOS, you may have to reduce the
  data structure to deal with the limited memory. In addition, BP7 does not
  support 32-bit Integer type, it causes some Integer variables would have
  to be converted into LongInt variables.
- If you prefer to compile under Delphi, you can simply convert the source
  code as follows:
  + Replace the type "Text" with the type "TextFile"
  + Change all procedure calls "Assign(., .)" to "AssignFile(., .)" and
    "Close(.)" to "CloseFile(.)"
  + Remove the {$MODE DELPHI} and add the {$APPTYPE CONSOLE} compiler 
    directive to the beginning of this program
-----------------------------------------------------------------
Please report any errors to: dsaptextbook@gmail.com, MANY THANKS!
-----------------------------------------------------------------
*)
const
  InputFile  = '';
  OutputFile = '';
  maxV = 1000;
  maxE = (maxV - 1) * maxV div 2;
type
  TEdge = record    			
    u, v, c: Integer;		
    Mark: Boolean;			
  end;
var
  e: array[1..maxE] of TEdge; 			
  Lab: array[1..maxV] of Integer;		
  n, m: Integer;
  Connected: Boolean;
 
 
procedure PrintResult;
var
  i: Integer;
begin
  for i:=35 downto 0 do WriteLn(i);
end;
 
begin
  PrintResult;
end.
 

eystLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSt9Cnt8ICAgICAgICBUaGUgVGV4dGJvb2sgaW4gRGF0YSBTdHJ1Y3R1cmUsIEFsZ29yaXRobXMgYW5kIFByb2dyYW1taW5nICAgICAgICB8fQp7fCAgICAgICAgICAgICAgaHR0cDovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmMuanAvfmhvYW5nbGUvRFNBUFRleHRib29rLyAgICAgICAgICAgICAgIHx9Cnt8ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB8fQp7fCAgICBQcm9ncmFtOiBGaW5kaW5nX3RoZV9NaW5pbXVtX1NwYW5uaW5nX1RyZWVfdXNpbmdfS3J1c2thbF9BbGdvcml0aG0gICAgfH0Ke3wgICAgICAgICAgICAgICAgICAgICAgICAgV3JpdHRlbiBieSBMZSBNaW5oIEhvYW5nICAgICAgICAgICAgICAgICAgICAgICAgIHx9Cnt8ICAgICAgICAgICAgICAgICAgICAgIEVtYWlsOiBkc2FwdGV4dGJvb2tAZ21haWwuY29tICAgICAgICAgICAgICAgICAgICAgICB8fQp7Ky0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tK30KCnskTU9ERSBERUxQSEl9ICgqVGhpcyBwcm9ncmFtIHVzZXMgMzItYml0IEludGVnZXIgWy0yXjMxIC4uIDJeMzEgLSAxXSopCnByb2dyYW0gRmluZGluZ190aGVfTWluaW11bV9TcGFubmluZ19UcmVlX3VzaW5nX0tydXNrYWxfQWxnb3JpdGhtOwooKgpJTVBPUlRBTlQgTk9URVMgRk9SIENPTVBBVElCSUxJVFk6Cj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLSBUaGlzIHByb2dyYW0gaXMgZXNwZWNpYWxseSB3cml0dGVuIGZvciBydW5uaW5nIHVuZGVyIFdpbmRvd3MgMzIgYml0IGFuZAogIEZyZWUgUGFzY2FsIElERS4gVGhlcmVmb3JlLCAzMi1iaXQgSW50ZWdlciB0eXBlIGlzIHVzZWQgdG8gcmVzdWx0IGluIHRoZQogIGJlc3QgcGVyZm9ybWFuY2Ugd2l0aCB0aGUgeyRNT0RFIERFTFBISX0gY29tcGlsZXIgZGlyZWN0aXZlIG9mIEZQSyBmb3IKICBXaW5kb3dzLgotIElmIHlvdSB1c2UgQm9ybGFuZCBUdXJibyBQYXNjYWwgNyBmb3IgRE9TLCB5b3UgbWF5IGhhdmUgdG8gcmVkdWNlIHRoZQogIGRhdGEgc3RydWN0dXJlIHRvIGRlYWwgd2l0aCB0aGUgbGltaXRlZCBtZW1vcnkuIEluIGFkZGl0aW9uLCBCUDcgZG9lcyBub3QKICBzdXBwb3J0IDMyLWJpdCBJbnRlZ2VyIHR5cGUsIGl0IGNhdXNlcyBzb21lIEludGVnZXIgdmFyaWFibGVzIHdvdWxkIGhhdmUKICB0byBiZSBjb252ZXJ0ZWQgaW50byBMb25nSW50IHZhcmlhYmxlcy4KLSBJZiB5b3UgcHJlZmVyIHRvIGNvbXBpbGUgdW5kZXIgRGVscGhpLCB5b3UgY2FuIHNpbXBseSBjb252ZXJ0IHRoZSBzb3VyY2UKICBjb2RlIGFzIGZvbGxvd3M6CiAgKyBSZXBsYWNlIHRoZSB0eXBlICJUZXh0IiB3aXRoIHRoZSB0eXBlICJUZXh0RmlsZSIKICArIENoYW5nZSBhbGwgcHJvY2VkdXJlIGNhbGxzICJBc3NpZ24oLiwgLikiIHRvICJBc3NpZ25GaWxlKC4sIC4pIiBhbmQKICAgICJDbG9zZSguKSIgdG8gIkNsb3NlRmlsZSguKSIKICArIFJlbW92ZSB0aGUgeyRNT0RFIERFTFBISX0gYW5kIGFkZCB0aGUgeyRBUFBUWVBFIENPTlNPTEV9IGNvbXBpbGVyIAogICAgZGlyZWN0aXZlIHRvIHRoZSBiZWdpbm5pbmcgb2YgdGhpcyBwcm9ncmFtCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tClBsZWFzZSByZXBvcnQgYW55IGVycm9ycyB0bzogZHNhcHRleHRib29rQGdtYWlsLmNvbSwgTUFOWSBUSEFOS1MhCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiopCmNvbnN0CiAgSW5wdXRGaWxlICA9ICcnOwogIE91dHB1dEZpbGUgPSAnJzsKICBtYXhWID0gMTAwMDsKICBtYXhFID0gKG1heFYgLSAxKSAqIG1heFYgZGl2IDI7CnR5cGUKICBURWRnZSA9IHJlY29yZCAgICAJCQkKICAgIHUsIHYsIGM6IEludGVnZXI7CQkKICAgIE1hcms6IEJvb2xlYW47CQkJCiAgZW5kOwp2YXIKICBlOiBhcnJheVsxLi5tYXhFXSBvZiBURWRnZTsgCQkJCiAgTGFiOiBhcnJheVsxLi5tYXhWXSBvZiBJbnRlZ2VyOwkJCiAgbiwgbTogSW50ZWdlcjsKICBDb25uZWN0ZWQ6IEJvb2xlYW47CgoKcHJvY2VkdXJlIFByaW50UmVzdWx0Owp2YXIKICBpOiBJbnRlZ2VyOwpiZWdpbgogIGZvciBpOj0zNSBkb3dudG8gMCBkbyBXcml0ZUxuKGkpOwplbmQ7CgpiZWdpbgogIFByaW50UmVzdWx0OwplbmQuCg==

NyAyMQoxIDIgNTQ3MTUyCjEgMyA1MDkxNTcKMSA0IDUzOTI4MgoxIDUgNTQxNjQ1ICAgICAgICAgCjEgNiA0NTg0MzMKMSA3IDM4NTE3M+KAqAoyIDMgMTMxNTI4CjIgNCA5MjczNQoyIDUgMTUwNTExCjIgNiA5NDQ0MAoyIDcgMTk0NTQyCjMgNCAyMTY2MDAKMyA1IDI3MjQwMQozIDYgMTU3MTc2CjMgNyAxMjQwNzcKNCA1IDU3Nzg1CjQgNiA5NzMyMwo0IDcgMjQyMjMyCjUgNiAxMzY2NjMKNSA3IDI4Mzg2Mgo2IDcgMTQ3NDI2

7 21
1 2 547152
1 3 509157
1 4 539282
1 5 541645         
1 6 458433
1 7 385173

2 3 131528
2 4 92735
2 5 150511
2 6 94440
2 7 194542
3 4 216600
3 5 272401
3 6 157176
3 7 124077
4 5 57785
4 6 97323
4 7 242232
5 6 136663
5 7 283862
6 7 147426