// Minimalne drzewo rozpinające
// Algorytm Kruskala
// Data: 6.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

// Definicja obiektu kolejki priorytetowej
//----------------------------------------
type
  Edge = record
    v1, v2  : integer;     // Wierzchołki krawędzi
    weight : integer;      // Waga krawędzi
  end;

  Queue = object
    private
      Heap : array of Edge;
      hpos : integer;
    public
      constructor init (n : integer);
      destructor  destroy;
      function    front : Edge;
      procedure   push (e : Edge);
      procedure   pop;
  end;

// Definicja obiektu struktury zbiorów rozłącznych
//------------------------------------------------
  DSNode = record
    up   : integer;
    rank : integer;
  end;

  DSStruct = object
    private
      Z : array of DSNode;
    public
      constructor init (n : integer);
      destructor  destroy;
      procedure   MakeSet (v : integer);
      function    FindSet (v : integer) : integer;
      procedure   UnionSets (e : Edge);
  end;

// Definicja obiektu minimalnego drzewa rozpinającego
//---------------------------------------------------
  PTNode = ^TNode;
  TNode = record
    next   : PTNode;
    v      : integer;
    weight : integer;
  end;

  MSTree = object
    private
      A : array of PTNode; // Tablica list sąsiedztwa
      Alen : integer;      // Liczba komórek w tablicy
      weight : integer;    // Waga całego drzewa
    public
      constructor init (n : integer);
      destructor  destroy;
      procedure   addEdge (e : Edge);
      procedure   print;
  end;

// Definicje metod obiektu Queue
//------------------------------

// Konstruktor - tworzy n elementową tablicę heap na kopiec
//---------------------------------------------------------
constructor Queue.init (n : integer);
begin
  SetLength (Heap, n);  // Tworzymy tablicę
  hpos := 0;              // Pozycja w kopcu
end;

// Destruktor - usuwa kopiec z pamięci
//------------------------------------
destructor Queue.destroy;
begin
  SetLength (Heap, 0);
end;

// Zwraca krawędź z początku kopca
//--------------------------------
function Queue.front : Edge;
begin
  front := Heap [0];
end;

// Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
//----------------------------------------------------------
procedure Queue.push (e : Edge);
var
  i, j : integer;
begin
  i := hpos;              // i ustawiamy na koniec kopca
  inc (hpos);           // W kopcu będzie o 1 element wiecej
  j := (i - 1) Shr 1;   // Obliczamy pozycję rodzica

  // Szukamy miejsca w kopcu dla e

  while(i > 0) and (Heap [j].weight > e.weight) do
  begin
    Heap [i] := Heap [j];
    i := j;
    j := (i - 1) Shr 1;
  end;

  Heap [i] := e;        // Krawędź e wstawiamy do kopca
end;

// Usuwa korzeń z kopca i odtwarza jego strukturę
//-----------------------------------------------
procedure Queue.pop;
var
  i, j : integer;
  e   : Edge;
begin
  if hpos > 0 then
  begin
    dec (hpos);

    e := Heap [hpos];

    i := 0;
    j := 1;

    while j < hpos do
    begin
      if(j + 1 < hpos) and (Heap [j + 1].weight < Heap [j].weight) then inc (j);
      if e.weight <= Heap [j].weight then break;
      Heap [i] := Heap [j];
      i := j;
      j := (j Shl 1) + 1;
    end;

    Heap [i] := e;
  end;
end;

// Definicje metod obiektu DSStruct
//---------------------------------

// Konstruktor
constructor DSStruct.init (n : integer);
begin
  SetLength (Z, n);     // Tworzymy tablicę dla elementów zbiorów
end;

// Destruktor
//-----------
destructor DSStruct.destroy;
begin
  SetLength (Z, 0);     // Usuwamy tablicę ze zbiorami
end;

// Tworzy wpis w tablicy Z
//------------------------
procedure DSStruct.MakeSet (v : integer);
begin
  Z [v].up   := v;
  Z [v].rank := 0;
end;

// Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v
//----------------------------------------------------------------
function DSStruct.FindSet (v : integer) : integer;
begin
  if Z [v].up <> v then Z [v].up := FindSet (Z [v].up);
  FindSet := Z [v].up;
end;

// Łączy ze sobą zbiory z v i u
//-----------------------------
procedure DSStruct.UnionSets (e : Edge);
var
  ru, rv : integer;
begin
  ru := FindSet (e.v1); // Wyznaczamy korzeń drzewa z węzłem u
  rv := FindSet (e.v2); // Wyznaczamy korzeń drzewa z węzłem v
  if ru <> rv then        // Korzenie muszą być różne
  begin
    if Z [ru].rank > Z [rv].rank then // Porównujemy rangi drzew
       Z [rv].up := ru  // ru większe, dołączamy rv
    else
    begin
      Z [ru].up := rv;  // równe lub rv większe, dołączamy ru
      if Z [ru].rank = Z [rv].rank then inc (Z [rv].rank);
    end;
  end;
end;

// Definicje metod obiektu MSTree
//-------------------------------

// Konstruktor - tworzy tablicę pustych list sąsiedztwa
//-----------------------------------------------------
constructor MSTree.init (n : integer);
var
  i : integer;
begin
  SetLength (A, n);    // Tworzymy tablicę dynamiczną
  for i := 0 to n - 1 do A [i] := nil; // i wypełniamy ją pustymi listami
  Alen := n - 1;         // Zapamiętujemy długość tablicy
  weight := 0;           // Zerujemy wagę drzewa
end;

// Destruktor - usuwa listy oraz tablicę sąsiedztwa
//-------------------------------------------------
destructor MSTree.destroy;
var
  i : integer;
  p, r : PTNode;
begin
  for i := 0 to Alen do
  begin
    p := A [i];
    while p <> nil do
    begin
      r := p;            // Zapamiętujemy wskazanie
      p := p^.next;      // Przesuwamy się do następnego elementu listy
      dispose (r);     // Usuwamy element
    end;
  end;
  SetLength (A, 0);    // Usuwamy tablicę list sąsiedztwa
end;

// Dodaje krawędź do drzewa
//-------------------------
procedure MSTree.addEdge (e : Edge);
var
  p : PTNode;
begin
  inc (weight, e.weight); // Do wagi drzewa dodajemy wagę krawędzi
  new (p);             // Tworzymy nowy węzeł
  p^.v := e.v2;          // Wierzchołek końcowy
  p^.weight := e.weight; // Waga krawędzi
  p^.next := A [e.v1]; // Dodajemy p do listy wierzchołka v1
  A [e.v1] := p;

  new (p);             // To samo dla krawędzi odwrotnej
  p^.v := e.v1;          // Wierzchołek końcowy
  p^.weight := e.weight; // Waga krawędzi
  p^.next := A [e.v2]; // Dodajemy p do listy wierzchołka v2
  A [e.v2] := p;
end;

// Wyświetla zawartość drzewa oraz jego wagę
//------------------------------------------
procedure MSTree.print;
var
  i : integer;
  p : PTNode;
begin
  writeln;
  for i := 0 to Alen do
  begin
    write ('Vertex ', i, ' - ');
    p := A [i];
    while p <> nil do
    begin
      write (p^.v, ':', p^.weight, ' ');
      p := p^.next;
    end;
    writeln;
  end;
  writeln;
  writeln('Minimal Spanning Tree Weight = ', weight);
  writeln;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m : integer;       // Liczba wierzchołków i krawędzi
  e   : Edge;
  i   : integer;
  Z   : DSStruct;       // Struktura zbiorów rozłącznych
  Q   : Queue;          // Kolejka priorytetowa oparta na kopcu
  T   : MSTree;         // Minimalne drzewo rozpinające
begin
  read (n, m);        // Czytamy liczbę wierzchołków i krawędzi

  Z.init (n);         // Inicjujemy strukturę zbiorów rozłącznych
  Q.init (m);         // Inicjujemy kolejkę priorytetową
  T.init (n);         // Inicjujemy minimalne drzewo rozpinające

  for i := 0 to n - 1 do
    Z.MakeSet (i);    // Dla każdego wierzchołka tworzymy osobny zbiór

  for i := 1 to m do
  begin
    read (e.v1, e.v2, e.weight); // Odczytujemy kolejne krawędzie grafu
    Q.push (e);       // i umieszczamy je w kolejce priorytetowej
  end;

  for i := 1 to n - 1 do
  begin
    repeat
      e := Q.front;     // Pobieramy z kolejki krawędź
      Q.pop;            // Krawędź usuwamy z kolejki
    until Z.FindSet (e.v1) <> Z.FindSet (e.v2);
    T.addEdge (e);    // Dodajemy krawędź do drzewa
    Z.UnionSets (e);  // Zbiory z wierzchołkami łączymy ze sobą
  end;

  // Wyświetlamy wyniki

  T.print;

  // Usuwamy struktury

  Z.destroy;
  Q.destroy;
  T.destroy;
end.

// Minimalne drzewo rozpinające
// Algorytm Kruskala
// Data: 6.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>

using namespace std;

// Definicja obiektu kolejki priorytetowej
//----------------------------------------
struct Edge
{
  int v1, v2, weight;      // Wierzchołki krawędzi, waga krawędzi
};

class Queue
{
  private:
    Edge * Heap;
    int hpos;
  public:
    Queue (int n);
    ~Queue();
    Edge front();
    void push (Edge e);
    void pop();
};

// Definicja obiektu struktury zbiorów rozłącznych
//------------------------------------------------
struct DSNode
{
  int up, rank;
};

class DSStruct
{
  private:
    DSNode * Z;
  public:
    DSStruct (int n);
    ~DSStruct();
    void MakeSet (int v);
    int FindSet (int v);
    void UnionSets (Edge e);
};

// Definicja obiektu minimalnego drzewa rozpinającego
//---------------------------------------------------
struct TNode
{
  TNode * next;
  int v, weight;
};

class MSTree
{
  private:
    TNode ** A;            // Tablica list sąsiedztwa
    int Alen;              // Liczba komórek w tablicy
    int weight;            // Waga całego drzewa
  public:
    MSTree (int n);
    ~MSTree();
    void addEdge (Edge e);
    void print();
};

// Definicje metod obiektu Queue
//------------------------------

// Konstruktor - tworzy n elementową tablicę heap na kopiec
//---------------------------------------------------------
Queue::Queue (int n)
{
  Heap = new Edge [n];   // Tworzymy tablicę
  hpos = 0;                // Pozycja w kopcu
}

// Destruktor - usuwa kopiec z pamięci
//------------------------------------
Queue::~Queue()
{
  delete [] Heap;
}

// Zwraca krawędź z początku kopca
//--------------------------------
Edge Queue::front()
{
  return Heap [0];
}

// Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
//----------------------------------------------------------
void Queue::push (Edge e)
{
  int i, j;

  i = hpos++;              // i ustawiamy na koniec kopca
  j = (i - 1) >> 1;      // Obliczamy pozycję rodzica

  // Szukamy miejsca w kopcu dla e

  while(i && (Heap [j].weight > e.weight))
  {
    Heap [i] = Heap [j];
    i = j;
    j = (i - 1) >> 1;
  }

  Heap [i] = e;          // Krawędź e wstawiamy do kopca
}

// Usuwa korzeń z kopca i odtwarza jego strukturę
//-----------------------------------------------
void Queue::pop()
{
  int i, j;
  Edge e;

  if(hpos)
  {
    e = Heap [--hpos];

    i = 0;
    j = 1;

    while(j < hpos)
    {
      if((j + 1 < hpos) && (Heap [j + 1].weight < Heap [j].weight)) j++;
      if(e.weight <= Heap [j].weight) break;
      Heap [i] = Heap [j];
      i = j;
      j = (j << 1) + 1;
    }

    Heap [i] = e;
  }
}

// Definicje metod obiektu DSStruct
//---------------------------------

// Konstruktor
DSStruct::DSStruct (int n)
{
  Z = new DSNode [n];    // Tworzymy tablicę dla elementów zbiorów
}

// Destruktor
//-----------
DSStruct::~DSStruct()
{
  delete [] Z;            // Usuwamy tablicę ze zbiorami
}

// Tworzy wpis w tablicy Z
//------------------------
void DSStruct::MakeSet (int v)
{
  Z [v].up   = v;
  Z [v].rank = 0;
}

// Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v
//----------------------------------------------------------------
int DSStruct::FindSet (int v)
{
  if(Z [v].up != v) Z [v].up = FindSet (Z [v].up);
  return Z [v].up;
}

// Łączy ze sobą zbiory z v i u
//-----------------------------
void DSStruct::UnionSets (Edge e)
{
  int ru, rv;

  ru = FindSet (e.v1);   // Wyznaczamy korzeń drzewa z węzłem u
  rv = FindSet (e.v2);   // Wyznaczamy korzeń drzewa z węzłem v
  if(ru != rv)           // Korzenie muszą być różne
  {
    if(Z [ru].rank > Z [rv].rank) // Porównujemy rangi drzew
      Z [rv].up = ru;    // ru większe, dołączamy rv
    else
    {
      Z [ru].up = rv;    // równe lub rv większe, dołączamy ru
      if(Z [ru].rank == Z [rv].rank) Z [rv].rank++;
    }
  }
}

// Definicje metod obiektu MSTree
//-------------------------------

// Konstruktor - tworzy tablicę pustych list sąsiedztwa
//-----------------------------------------------------
MSTree::MSTree (int n)
{
  int i;

  A = new TNode * [n];   // Tworzymy tablicę dynamiczną
  for(i = 0; i < n; i++) A [i] = NULL; // i wypełniamy ją pustymi listami
  Alen = n - 1;            // Zapamiętujemy długość tablicy
  weight = 0;              // Zerujemy wagę drzewa
}

// Destruktor - usuwa listy oraz tablicę sąsiedztwa
//-------------------------------------------------
MSTree::~MSTree()
{
  int i;
  TNode *p, *r;

  for(i = 0; i <= Alen; i++)
  {
    p = A [i];
    while(p)
    {
      r = p;               // Zapamiętujemy wskazanie
      p = p->next;         // Przesuwamy się do następnego elementu listy
      delete r;            // Usuwamy element
    }
  }

  delete [] A;            // Usuwamy tablicę list sąsiedztwa
}

// Dodaje krawędź do drzewa
//-------------------------
void MSTree::addEdge (Edge e)
{
  TNode *p;

  weight += e.weight;      // Do wagi drzewa dodajemy wagę krawędzi
  p = new TNode;           // Tworzymy nowy węzeł
  p->v = e.v2;             // Wierzchołek końcowy
  p->weight = e.weight;    // Waga krawędzi
  p->next = A [e.v1];    // Dodajemy p do listy wierzchołka v1
  A [e.v1] = p;

  p = new TNode;           // To samo dla krawędzi odwrotnej
  p->v = e.v1;             // Wierzchołek końcowy
  p->weight = e.weight;    // Waga krawędzi
  p->next = A [e.v2];    // Dodajemy p do listy wierzchołka v2
  A [e.v2] = p;
}

// Wyświetla zawartość drzewa oraz jego wagę
//------------------------------------------
void MSTree::print()
{
  int i;
  TNode *p;

  cout << endl;
  for(i = 0; i <= Alen; i++)
  {
    cout << "Vertex " << i << " - ";
    for(p = A [i]; p; p = p->next) cout << p->v << ":" << p->weight << " ";
    cout << endl;
  }
  cout << endl << endl << "Minimal Spanning Tree Weight = " << weight << endl << endl;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m;                // Liczba wierzchołków i krawędzi
  Edge e;
  int i;

  cin >> n >> m;           // Czytamy liczbę wierzchołków i krawędzi

  DSStruct Z (n);        // Struktura zbiorów rozłącznych
  Queue Q (m);           // Kolejka priorytetowa oparta na kopcu
  MSTree T (n);          // Minimalne drzewo rozpinające

  for(i = 0; i < n; i++)
    Z.MakeSet (i);       // Dla każdego wierzchołka tworzymy osobny zbiór

  for(i = 0; i < m; i++)
  {
    cin >> e.v1 >> e.v2 >> e.weight; // Odczytujemy kolejne krawędzie grafu
    Q.push (e);          // i umieszczamy je w kolejce priorytetowej
  }

  for(i = 1; i < n; i++) // Pętla wykonuje się n - 1 razy !!!
  {
    do
    {
      e = Q.front();      // Pobieramy z kolejki krawędź
      Q.pop();            // Krawędź usuwamy z kolejki
    } while(Z.FindSet (e.v1) == Z.FindSet (e.v2));
    T.addEdge (e);       // Dodajemy krawędź do drzewa
    Z.UnionSets (e);     // Zbiory z wierzchołkami łączymy ze sobą
  }

  // Wyświetlamy wyniki

  T.print();

  return 0;}

' Minimalne drzewo rozpinające
' Algorytm Kruskala
' Data: 6.04.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------

' Definicja obiektu kolejki priorytetowej
'----------------------------------------
Type Edge
  v1 As Integer         ' Wierzchołki krawędzi, waga krawędzi
  v2 As Integer
  weight As Integer
End Type

Type Queue
  Private:
    Heap As Edge Ptr
    hpos As Integer
  Public:
    Declare Constructor (ByVal n As Integer)
    Declare Destructor()
    Declare Function front() As Edge
    Declare Sub push (ByVal e As Edge)
    Declare Sub pop()
End Type

' Definicja obiektu struktury zbiorów rozłącznych
'------------------------------------------------
Type DSNode
  up As Integer
  rank As Integer
End Type

Type DSStruct
  Private:
    Z As DSNode Ptr
  Public:
    Declare Constructor (ByVal n As Integer)
    Declare Destructor()
    Declare Sub MakeSet (ByVal v As Integer)
    Declare Function FindSet (ByVal v As Integer) As Integer
    Declare Sub UnionSets (ByVal e As Edge)
End Type

' Definicja obiektu minimalnego drzewa rozpinającego
'---------------------------------------------------
Type TNode
  Next As TNode Ptr
  v As Integer
  weight As Integer
End Type

Type MSTree
  Private:
    A As TNode Ptr Ptr  ' Tablica list sąsiedztwa
    Alen As Integer     ' Liczba komórek w tablicy
    weight As Integer   ' Waga całego drzewa
  Public:
    Declare Constructor (ByVal n As Integer)
    Declare Destructor()
    Declare Sub addEdge (ByVal e As Edge)
    Declare Sub Tprint()
End Type

' Definicje metod obiektu Queue
'------------------------------

' Konstruktor - tworzy n elementową tablicę heap na kopiec
'---------------------------------------------------------
Constructor Queue (ByVal n As Integer)
  Heap = New Edge [n] ' Tworzymy tablicę
  hpos = 0              ' Pozycja w kopcu
End Constructor

' Destruktor - usuwa kopiec z pamięci
'------------------------------------
Destructor Queue()
  Delete [] Heap
End Destructor

' Zwraca krawędź z początku kopca
'--------------------------------
Function Queue.front() As Edge
  return Heap [0]
End Function

' Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
'----------------------------------------------------------
Sub Queue.push (ByVal e As Edge)
  Dim As Integer i, j

  i = hpos              ' i ustawiamy na koniec kopca
  hpos += 1
  j = (i - 1) Shr 1   ' Obliczamy pozycję rodzica

  ' Szukamy miejsca w kopcu dla e

  while(i > 0) AndAlso (Heap [j].weight > e.weight)
    Heap [i] = Heap [j]
    i = j
    j = (i - 1) Shr 1
  Wend

  Heap [i] = e        ' Krawędź e wstawiamy do kopca
End Sub

' Usuwa korzeń z kopca i odtwarza jego strukturę
'-----------------------------------------------
Sub Queue.pop()
  Dim As Integer i, j
  Dim As Edge e

  If hpos > 0 Then
    hpos -= 1
    e = Heap [hpos]

    i = 0
    j = 1

    While j < hpos
      if(j + 1 < hpos) AndAlso (Heap [j + 1].weight < Heap [j].weight) Then j += 1
      If e.weight <= Heap [j].weight Then Exit While
      Heap [i] = Heap [j]
      i = j
      j = (j Shl 1) + 1
    Wend

    Heap [i] = e
  End If
End Sub

' Definicje metod obiektu DSStruct
'---------------------------------

' Konstruktor
Constructor DSStruct (ByVal n As Integer)
  Z = New DSNode [n]  ' Tworzymy tablicę dla elementów zbiorów
End Constructor

' Destruktor
'-----------
Destructor DSStruct()
  Delete [] Z          ' Usuwamy tablicę ze zbiorami
End Destructor

' Tworzy wpis w tablicy Z
'------------------------
Sub DSStruct.MakeSet (ByVal v As Integer)
  Z [v].up   = v
  Z [v].rank = 0
End Sub

' Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v
'----------------------------------------------------------------
Function DSStruct.FindSet (ByVal v As Integer) As Integer
  If Z [v].up <> v Then Z [v].up = FindSet (Z [v].up)
  return Z [v].up
End Function

' Łączy ze sobą zbiory z v i u
'-----------------------------
Sub DSStruct.UnionSets (ByVal e As Edge)
  Dim As Integer ru, rv

  ru = FindSet (e.v1) ' Wyznaczamy korzeń drzewa z węzłem u
  rv = FindSet (e.v2) ' Wyznaczamy korzeń drzewa z węzłem v
  if ru <> rv Then      ' Korzenie muszą być różne
    If Z [ru].rank > Z [rv].rank Then ' Porównujemy rangi drzew
      Z [rv].up = ru  ' ru większe, dołączamy rv
    Else
      Z [ru].up = rv ' równe lub rv większe, dołączamy ru
      If Z [ru].rank = Z [rv].rank Then Z [rv].rank += 1
    End If
  End If
End Sub

' Definicje metod obiektu MSTree
'-------------------------------

' Konstruktor - tworzy tablicę pustych list sąsiedztwa
'-----------------------------------------------------
Constructor MSTree (ByVal n As Integer)
  Dim As Integer i

  A = New TNode Ptr [n] ' Tworzymy tablicę dynamiczną
  For i = 0 To n - 1
  	 A [i] = 0     ' i wypełniamy ją pustymi listami
  Next
  Alen = n - 1         ' Zapamiętujemy długość tablicy
  weight = 0           ' Zerujemy wagę drzewa
End Constructor

' Destruktor - usuwa listy oraz tablicę sąsiedztwa
'-------------------------------------------------
Destructor MSTree()
  Dim As Integer i
  Dim As TNode Ptr p, r

  For i = 0 to Alen
    p = A [i]
    While p
      r = p            ' Zapamiętujemy wskazanie
      p = p->Next      ' Przesuwamy się do następnego elementu listy
      Delete r         ' Usuwamy element
    Wend
  Next

  Delete [] A         ' Usuwamy tablicę list sąsiedztwa
End Destructor

' Dodaje krawędź do drzewa
'-------------------------
Sub MSTree.addEdge (ByVal e As Edge)
  Dim As TNode Ptr p

  weight += e.weight   ' Do wagi drzewa dodajemy wagę krawędzi
  p = New TNode        ' Tworzymy nowy węzeł
  p->v = e.v2          ' Wierzchołek końcowy
  p->weight = e.weight ' Waga krawędzi
  p->next = A [e.v1] ' Dodajemy p do listy wierzchołka v1
  A [e.v1] = p

  p = New TNode        ' To samo dla krawędzi odwrotnej
  p->v = e.v1          ' Wierzchołek końcowy
  p->weight = e.weight ' Waga krawędzi
  p->next = A [e.v2] ' Dodajemy p do listy wierzchołka v2
  A [e.v2] = p
End Sub

' Wyświetla zawartość drzewa oraz jego wagę
'------------------------------------------
Sub MSTree.Tprint()
  Dim As Integer i
  Dim As TNode Ptr p

  Print
  For i = 0 to Alen
    Print "Vertex";i;" - ";
    p = A [i]
    While p
    	Print Using "&:& ";p->v;p->weight;
    	p = p->Next
    Wend
    Print
  Next
  Print
  Print "Minimal Spanning Tree Weight =";weight
  Print
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As integer n, m ' Liczba wierzchołków i krawędzi
Dim As Edge e
Dim As Integer i

Open Cons For Input As #1

Input #1, n, m      ' Czytamy liczbę wierzchołków i krawędzi

Dim As DSStruct Z = n ' Struktura zbiorów rozłącznych
Dim As Queue Q = m  ' Kolejka priorytetowa oparta na kopcu
Dim As MSTree T = n ' Minimalne drzewo rozpinające

For i = 0 To n - 1
  Z.MakeSet (i)   ' Dla każdego wierzchołka tworzymy osobny zbiór
Next

For i = 1 To m
  Input #1, e.v1, e.v2, e.weight ' Odczytujemy kolejne krawędzie grafu
  Q.push (e)      ' i umieszczamy je w kolejce priorytetowej
Next

Close #1

For i = 1 To n - 1  ' Pętla wykonuje się n - 1 razy !!!
  Do
    e = Q.front()  ' Pobieramy z kolejki krawędź
    Q.pop()        ' Krawędź usuwamy z kolejki
  Loop While Z.FindSet (e.v1) = Z.FindSet (e.v2)
  T.addEdge (e)   ' Dodajemy krawędź do drzewa
  Z.UnionSets (e) ' Zbiory z wierzchołkami łączymy ze sobą
Next

' Wyświetlamy wyniki

T.Tprint()

End

// Minimalne drzewo rozpinające
// Algorytm Prima
// Data: 11.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

// Definicja obiektu kolejki priorytetowej
//----------------------------------------
type
  Edge = record
    v1, v2  : integer;          // Wierzchołki krawędzi
    weight : integer;           // Waga krawędzi
  end;

  Queue = object
    private
      Heap : array of Edge;
      hpos : integer;
    public
      constructor init (n : integer);
      destructor  destroy;
      function    front : Edge;
      procedure   push (e : Edge);
      procedure   pop;
  end;

// Definicja obiektu minimalnego drzewa rozpinającego
//---------------------------------------------------
  PTNode = ^TNode;
  TNode = record
    next   : PTNode;
    v      : integer;
    weight : integer;
  end;

  MSTree = object
    private
      A      : array of PTNode; // Tablica list sąsiedztwa
      Alen   : integer;         // Liczba komórek w tablicy
      weight : integer;         // Waga całego drzewa
    public
      constructor init (n : integer);
      destructor  destroy;
      procedure   addEdge (e : Edge);
      function    getAList (n : integer) : PTNode;
      procedure   print;
  end;

// Definicje metod obiektu Queue
//------------------------------

// Konstruktor - tworzy n elementową tablicę heap na kopiec
//---------------------------------------------------------
constructor Queue.init (n : integer);
begin
  SetLength (Heap, n);        // Tworzymy tablicę
  hpos := 0;                    // Pozycja w kopcu
end;

// Destruktor - usuwa kopiec z pamięci
//------------------------------------
destructor Queue.destroy;
begin
  SetLength (Heap, 0);
end;

// Zwraca krawędź z początku kopca
//--------------------------------
function Queue.front : Edge;
begin
  front := Heap [0];
end;

// Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
//----------------------------------------------------------
procedure Queue.push (e : Edge);
var
  i, j : integer;
begin
  i := hpos;                    // i ustawiamy na koniec kopca
  inc (hpos);                 // W kopcu będzie o 1 element wiecej
  j := (i - 1) Shr 1;         // Obliczamy pozycję rodzica

  // Szukamy miejsca w kopcu dla e

  while(i > 0) and (Heap [j].weight > e.weight) do
  begin
    Heap [i] := Heap [j];
    i := j;
    j := (i - 1) Shr 1;
  end;

  Heap [i] := e;              // Krawędź e wstawiamy do kopca
end;

// Usuwa korzeń z kopca i odtwarza jego strukturę
//-----------------------------------------------
procedure Queue.pop;
var
  i, j : integer;
  e   : Edge;
begin
  if hpos > 0 then
  begin
    dec (hpos);

    e := Heap [hpos];

    i := 0;
    j := 1;

    while j < hpos do
    begin
      if(j + 1 < hpos) and (Heap [j + 1].weight < Heap [j].weight) then inc (j);
      if e.weight <= Heap [j].weight then break;
      Heap [i] := Heap [j];
      i := j;
      j := (j Shl 1) + 1;
    end;

    Heap [i] := e;
  end;
end;

// Definicje metod obiektu MSTree
//-------------------------------

// Konstruktor - tworzy tablicę pustych list sąsiedztwa
//-----------------------------------------------------
constructor MSTree.init (n : integer);
var
  i : integer;
begin
  SetLength (A, n);           // Tworzymy tablicę dynamiczną
  for i := 0 to n - 1 do A [i] := nil; // i wypełniamy ją pustymi listami
  Alen := n - 1;                // Zapamiętujemy długość tablicy
  weight := 0;                  // Zerujemy wagę drzewa
end;

// Destruktor - usuwa listy oraz tablicę sąsiedztwa
//-------------------------------------------------
destructor MSTree.destroy;
var
  i : integer;
  p, r : PTNode;
begin
  for i := 0 to Alen do
  begin
    p := A [i];
    while p <> nil do
    begin
      r := p;                   // Zapamiętujemy wskazanie
      p := p^.next;             // Przesuwamy się do następnego elementu listy
      dispose (r);            // Usuwamy element
    end;
  end;
  SetLength (A, 0);           // Usuwamy tablicę list sąsiedztwa
end;

// Dodaje krawędź do drzewa
//-------------------------
procedure MSTree.addEdge (e : Edge);
var
  p : PTNode;
begin
  inc (weight, e.weight);     // Do wagi drzewa dodajemy wagę krawędzi
  new (p);                    // Tworzymy nowy węzeł
  p^.v := e.v2;                 // Wierzchołek końcowy
  p^.weight := e.weight;        // Waga krawędzi
  p^.next := A [e.v1];        // Dodajemy p do listy wierzchołka v1
  A [e.v1] := p;

  new (p);                    // To samo dla krawędzi odwrotnej
  p^.v := e.v1;                 // Wierzchołek końcowy
  p^.weight := e.weight;        // Waga krawędzi
  p^.next := A [e.v2];        // Dodajemy p do listy wierzchołka v2
  A [e.v2] := p;
end;

// Zwraca wskaźnik początku listy sąsiadów wierzchołka
//----------------------------------------------------
function MSTree.getAList (n : integer) : PTNode;
begin
  getAList := A [n];
end;

// Wyświetla zawartość drzewa oraz jego wagę
//------------------------------------------
procedure MSTree.print;
var
  i : integer;
  p : PTNode;
begin
  writeln;
  for i := 0 to Alen do
  begin
    write ('Vertex ', i, ' - ');
    p := A [i];
    while p <> nil do
    begin
      write (p^.v, ':', p^.weight, ' ');
      p := p^.next;
    end;
    writeln;
  end;
  writeln;
  writeln('Minimal Spanning Tree Weight = ', weight);
  writeln;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m : integer;               // Liczba wierzchołków i krawędzi
  e   : Edge;
  p   : PTNode;
  i, v : integer;
  Q   : Queue;                  // Kolejka priorytetowa oparta na kopcu
  G   : MSTree;                 // Graf
  T   : MSTree;                 // Minimalne drzewo rozpinające
  visited : array of boolean;   // Tablica odwiedzin
begin
  read (n, m);                // Czytamy liczbę wierzchołków i krawędzi

  Q.init (m);                 // Inicjujemy kolejkę priorytetową
  T.init (n);                 // Inicjujemy minimalne drzewo rozpinające
  G.init (n);                 // Inicjujemy graf
  SetLength (visited, n);     // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do
    visited [i] := false;     // Inicjujemy tablicę odwiedzin

  for i := 1 to m do
  begin
    read (e.v1, e.v2, e.weight); // Odczytujemy kolejne krawędzie grafu
    G.addEdge (e);            // i umieszczamy je w G
  end;

  // Tworzymy minimalne drzewo rozpinające

  v := 0;                       // Wierzchołek startowy
  visited [v] := true;        // Oznaczamy go jako odwiedzonego

  for i := 1 to n - 1 do        // Do drzewa dodamy n - 1 krawędzi grafu
  begin
    p := G.getAList (v);      // Pobieramy adres listy sąsiadów do p
    while p <> nil do           // Przeglądamy listę
    begin
      if not visited [p^.v] then
      begin
        e.v1 := v;              // Tworzymy krawędź
        e.v2 := p^.v;
        e.weight := p^.weight;
        Q.push (e);           // Dodajemy ją do kolejki priorytetowej
      end;
      p := p^.next;             // Następny sąsiad
    end;

    repeat
      e := Q.front;             // Pobieramy krawędź z kolejki
      Q.pop;
    until not visited [e.v2]; // Krawędź prowadzi poza drzewo?

    T.addEdge (e);            // Dodajemy krawędź do drzewa rozpinającego
    visited [e.v2] := true;   // Oznaczamy drugi wierzchołek jako odwiedzony
    v := e.v2;
  end;

  // Wyświetlamy wyniki

  T.print;

  // Usuwamy struktury

  Q.destroy;
  T.destroy;
  G.destroy;
  SetLength (visited, 0);
end.

// Minimalne drzewo rozpinające
// Algorytm Prima
// Data: 11.04.2014
// (C)2014 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>

using namespace std;

// Definicja obiektu kolejki priorytetowej
//----------------------------------------
struct Edge
{
  int v1, v2, weight;            // Wierzchołki krawędzi, waga krawędzi
};

class Queue
{
  private:
    Edge * Heap;
    int hpos;
  public:
    Queue (int n);
    ~Queue();
    Edge front();
    void push (Edge e);
    void pop();
};

// Definicja obiektu minimalnego drzewa rozpinającego
//---------------------------------------------------
struct TNode
{
  TNode * next;
  int v, weight;
};

class MSTree
{
  private:
    TNode ** A;                  // Tablica list sąsiedztwa
    int Alen;                    // Liczba komórek w tablicy
    int weight;                  // Waga całego drzewa
  public:
    MSTree (int n);
    ~MSTree();
    void addEdge (Edge e);
    TNode * getAList (int n);
    void print();
};

// Definicje metod obiektu Queue
//------------------------------

// Konstruktor - tworzy n elementową tablicę heap na kopiec
//---------------------------------------------------------
Queue::Queue (int n)
{
  Heap = new Edge [n];         // Tworzymy tablicę
  hpos = 0;                      // Pozycja w kopcu
}

// Destruktor - usuwa kopiec z pamięci
//------------------------------------
Queue::~Queue()
{
  delete [] Heap;
}

// Zwraca krawędź z początku kopca
//--------------------------------
Edge Queue::front()
{
  return Heap [0];
}

// Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
//----------------------------------------------------------
void Queue::push (Edge e)
{
  int i, j;

  i = hpos++;                    // i ustawiamy na koniec kopca
  j = (i - 1) >> 1;            // Obliczamy pozycję rodzica

  // Szukamy miejsca w kopcu dla e

  while(i && (Heap [j].weight > e.weight))
  {
    Heap [i] = Heap [j];
    i = j;
    j = (i - 1) >> 1;
  }

  Heap [i] = e;                // Krawędź e wstawiamy do kopca
}

// Usuwa korzeń z kopca i odtwarza jego strukturę
//-----------------------------------------------
void Queue::pop()
{
  int i, j;
  Edge e;

  if(hpos)
  {
    e = Heap [--hpos];

    i = 0;
    j = 1;

    while(j < hpos)
    {
      if((j + 1 < hpos) && (Heap [j + 1].weight < Heap [j].weight)) j++;
      if(e.weight <= Heap [j].weight) break;
      Heap [i] = Heap [j];
      i = j;
      j = (j << 1) + 1;
    }

    Heap [i] = e;
  }
}

// Definicje metod obiektu MSTree
//-------------------------------

// Konstruktor - tworzy tablicę pustych list sąsiedztwa
//-----------------------------------------------------
MSTree::MSTree (int n)
{
  int i;

  A = new TNode * [n];         // Tworzymy tablicę dynamiczną
  for(i = 0; i < n; i++) A [i] = NULL; // i wypełniamy ją pustymi listami
  Alen = n - 1;                  // Zapamiętujemy długość tablicy
  weight = 0;                    // Zerujemy wagę drzewa
}

// Destruktor - usuwa listy oraz tablicę sąsiedztwa
//-------------------------------------------------
MSTree::~MSTree()
{
  int i;
  TNode *p, *r;

  for(i = 0; i <= Alen; i++)
  {
    p = A [i];
    while(p)
    {
      r = p;                     // Zapamiętujemy wskazanie
      p = p->next;               // Przesuwamy się do następnego elementu listy
      delete r;                  // Usuwamy element
    }
  }

  delete [] A;                  // Usuwamy tablicę list sąsiedztwa
}

// Dodaje krawędź do drzewa
//-------------------------
void MSTree::addEdge (Edge e)
{
  TNode *p;

  weight += e.weight;            // Do wagi drzewa dodajemy wagę krawędzi
  p = new TNode;                 // Tworzymy nowy węzeł
  p->v = e.v2;                   // Wierzchołek końcowy
  p->weight = e.weight;          // Waga krawędzi
  p->next = A [e.v1];          // Dodajemy p do listy wierzchołka v1
  A [e.v1] = p;

  p = new TNode;                 // To samo dla krawędzi odwrotnej
  p->v = e.v1;                   // Wierzchołek końcowy
  p->weight = e.weight;          // Waga krawędzi
  p->next = A [e.v2];          // Dodajemy p do listy wierzchołka v2
  A [e.v2] = p;
}

// Zwraca wskaźnik początku listy sąsiadów wierzchołka
//----------------------------------------------------
TNode * MSTree::getAList (int n)
{
  return A [n];
}

// Wyświetla zawartość drzewa oraz jego wagę
//------------------------------------------
void MSTree::print()
{
  int i;
  TNode *p;

  cout << endl;
  for(i = 0; i <= Alen; i++)
  {
    cout << "Vertex " << i << " - ";
    for(p = A [i]; p; p = p->next) cout << p->v << ":" << p->weight << " ";
    cout << endl;
  }
  cout << endl << endl << "Minimal Spanning Tree Weight = " << weight << endl << endl;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m;                      // Liczba wierzchołków i krawędzi
  Edge e;
  TNode * p;
  int i, v;

  cin >> n >> m;                 // Czytamy liczbę wierzchołków i krawędzi

  Queue Q (m);                 // Kolejka priorytetowa oparta na kopcu
  MSTree T (n);                // Minimalne drzewo rozpinające
  MSTree G (n);                // Graf
  bool * visited = new bool [n];

  for(i = 0; i < n; i++)
    visited [i] = false;       // Inicjujemy tablicę odwiedzin

  for(i = 0; i < m; i++)
  {
    cin >> e.v1 >> e.v2 >> e.weight; // Odczytujemy kolejne krawędzie grafu
    G.addEdge (e);             // i umieszczamy je w G
  }

  // Tworzymy minimalne drzewo rozpinające

  v = 0;                         // Wierzchołek startowy
  visited [v] = true;          // Oznaczamy go jako odwiedzonego

  for(i = 1; i < n; i++)       // Do drzewa dodamy n - 1 krawędzi grafu
  {
    for(p = G.getAList (v); p; p = p->next) // Przeglądamy listę sąsiadów
      if(!visited [p->v])    // Jeśli sąsiad jest nieodwiedzony,
      {
        e.v1 = v;                // to tworzymy krawędź
        e.v2 = p->v;
        e.weight = p->weight;
        Q.push (e);            // Dodajemy ją do kolejki priorytetowej
      }

    do
    {
      e = Q.front();            // Pobieramy krawędź z kolejki
      Q.pop();
    } while(visited [e.v2]); // Krawędź prowadzi poza drzewo?

    T.addEdge (e);             // Dodajemy krawędź do drzewa rozpinającego
    visited [e.v2] = true;     // Oznaczamy drugi wierzchołek jako odwiedzony
    v = e.v2;
  }

  // Wyświetlamy wyniki

  T.print();

  delete [] visited;

  return 0;}

' Minimalne drzewo rozpinające
' Algorytm Prima
' Data: 11.04.2014
' (C)2014 mgr Jerzy Wałaszek
'--------------------------------

' Definicja obiektu kolejki priorytetowej
'----------------------------------------
Type Edge
  v1 As Integer            ' Wierzchołki krawędzi, waga krawędzi
  v2 As Integer
  weight As Integer
End Type

Type Queue
  Private:
    Heap As Edge Ptr
    hpos As Integer
  Public:
    Declare Constructor (ByVal n As Integer)
    Declare Destructor()
    Declare Function front() As Edge
    Declare Sub push (ByVal e As Edge)
    Declare Sub pop()
End Type

' Definicja obiektu minimalnego drzewa rozpinającego
'---------------------------------------------------
Type TNode
  Next As TNode Ptr
  v As Integer
  weight As Integer
End Type

Type MSTree
  Private:
    A As TNode Ptr Ptr     ' Tablica list sąsiedztwa
    Alen As Integer        ' Liczba komórek w tablicy
    weight As Integer      ' Waga całego drzewa
  Public:
    Declare Constructor (ByVal n As Integer)
    Declare Destructor()
    Declare Sub addEdge (ByVal e As Edge)
    Declare Function getAList (ByVal n As integer) As TNode Ptr
    Declare Sub Tprint()
End Type

' Definicje metod obiektu Queue
'------------------------------

' Konstruktor - tworzy n elementową tablicę heap na kopiec
'---------------------------------------------------------
Constructor Queue (ByVal n As Integer)
  Heap = New Edge [n]    ' Tworzymy tablicę
  hpos = 0                 ' Pozycja w kopcu
End Constructor

' Destruktor - usuwa kopiec z pamięci
'------------------------------------
Destructor Queue()
  Delete [] Heap
End Destructor

' Zwraca krawędź z początku kopca
'--------------------------------
Function Queue.front() As Edge
  return Heap [0]
End Function

' Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca
'----------------------------------------------------------
Sub Queue.push (ByVal e As Edge)
  Dim As Integer i, j

  i = hpos                 ' i ustawiamy na koniec kopca
  hpos += 1
  j = (i - 1) Shr 1      ' Obliczamy pozycję rodzica

  ' Szukamy miejsca w kopcu dla e

  while(i > 0) AndAlso (Heap [j].weight > e.weight)
    Heap [i] = Heap [j]
    i = j
    j = (i - 1) Shr 1
  Wend

  Heap [i] = e           ' Krawędź e wstawiamy do kopca
End Sub

' Usuwa korzeń z kopca i odtwarza jego strukturę
'-----------------------------------------------
Sub Queue.pop()
  Dim As Integer i, j
  Dim As Edge e

  If hpos > 0 Then
    hpos -= 1
    e = Heap [hpos]

    i = 0
    j = 1

    While j < hpos
      if(j + 1 < hpos) AndAlso (Heap [j + 1].weight < Heap [j].weight) Then j += 1
      If e.weight <= Heap [j].weight Then Exit While
      Heap [i] = Heap [j]
      i = j
      j = (j Shl 1) + 1
    Wend

    Heap [i] = e
  End If
End Sub

' Definicje metod obiektu MSTree
'-------------------------------

' Konstruktor - tworzy tablicę pustych list sąsiedztwa
'-----------------------------------------------------
Constructor MSTree (ByVal n As Integer)
  Dim As Integer i

  A = New TNode Ptr [n]  ' Tworzymy tablicę dynamiczną
  For i = 0 To n - 1
  	 A [i] = 0         ' i wypełniamy ją pustymi listami
  Next
  Alen = n - 1             ' Zapamiętujemy długość tablicy
  weight = 0               ' Zerujemy wagę drzewa
End Constructor

' Destruktor - usuwa listy oraz tablicę sąsiedztwa
'-------------------------------------------------
Destructor MSTree()
  Dim As Integer i
  Dim As TNode Ptr p, r

  For i = 0 to Alen
    p = A [i]
    While p
      r = p                ' Zapamiętujemy wskazanie
      p = p->Next          ' Przesuwamy się do następnego elementu listy
      Delete r             ' Usuwamy element
    Wend
  Next

  Delete [] A             ' Usuwamy tablicę list sąsiedztwa
End Destructor

' Dodaje krawędź do drzewa
'-------------------------
Sub MSTree.addEdge (ByVal e As Edge)
  Dim As TNode Ptr p

  weight += e.weight       ' Do wagi drzewa dodajemy wagę krawędzi
  p = New TNode            ' Tworzymy nowy węzeł
  p->v = e.v2              ' Wierzchołek końcowy
  p->weight = e.weight     ' Waga krawędzi
  p->next = A [e.v1]     ' Dodajemy p do listy wierzchołka v1
  A [e.v1] = p

  p = New TNode            ' To samo dla krawędzi odwrotnej
  p->v = e.v1              ' Wierzchołek końcowy
  p->weight = e.weight     ' Waga krawędzi
  p->next = A [e.v2]     ' Dodajemy p do listy wierzchołka v2
  A [e.v2] = p
End Sub

' Zwraca wskaźnik początku listy sąsiadów wierzchołka
'----------------------------------------------------
Function MSTree.getAList (ByVal n As integer) As TNode Ptr
  Return A [n]
End Function

' Wyświetla zawartość drzewa oraz jego wagę
'------------------------------------------
Sub MSTree.Tprint()
  Dim As Integer i
  Dim As TNode Ptr p

  Print
  For i = 0 to Alen
    Print "Vertex";i;" - ";
    p = A [i]
    While p
    	Print Using "&:& ";p->v;p->weight;
    	p = p->Next
    Wend
    Print
  Next
  Print
  Print "Minimal Spanning Tree Weight =";weight
  Print
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As integer n, m        ' Liczba wierzchołków i krawędzi
Dim As Edge e
Dim As TNode Ptr p
Dim As Integer i, v

Open Cons For Input As #1

Input #1, n, m             ' Czytamy liczbę wierzchołków i krawędzi

Dim As Queue Q = m         ' Kolejka priorytetowa oparta na kopcu
Dim As MSTree T = n        ' Minimalne drzewo rozpinające
Dim As MSTree G = n        ' Graf
Dim As Byte visited (0 To N - 1)
For i = 0 To n - 1
  visited (i) = 0        ' Inicjujemy tablicę odwiedzin
Next

For i = 1 To m
  Input #1, e.v1, e.v2, e.weight ' Odczytujemy kolejne krawędzie grafu
  G.addEdge (e)          ' i umieszczamy je w G
Next

Close #1

' Tworzymy minimalne drzewo rozpinające

v = 0                      ' Wierzchołek startowy
visited (v) = 1          ' Oznaczamy go jako odwiedzonego

For i = 2 To n             ' Do drzewa dodamy n - 1 krawędzi grafu
  p = G.getAList (v)     ' Przeglądamy listę sąsiadów     
  While p
    If visited (p->v) = 0 Then ' Jeśli sąsiad jest nieodwiedzony,
      e.v1 = v             ' to tworzymy krawędź
      e.v2 = p->v
      e.weight = p->weight
      Q.push (e)         ' Dodajemy ją do kolejki priorytetowej
    End If
    p = p->Next            ' Następny sąsiad
  Wend

  Do
    e = Q.front()         ' Pobieramy krawędź z kolejki
    Q.pop()
  Loop While visited (e.v2) = 1 ' Krawędź prowadzi poza drzewo?

  T.addEdge (e)          ' Dodajemy krawędź do drzewa rozpinającego
  visited (e.v2) = 1     ' Oznaczamy drugi wierzchołek jako odwiedzony
  v = e.v2
Next

' Wyświetlamy wyniki

T.Tprint()

End