// 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