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

// Definicja obiektu
// kolejki priorytetowej
//----------------------
type
  Edge = record
    // Wierzchołki krawędzi
    v1,v2 : integer;
    // Waga krawędzi
    weight : integer;
  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   make_set(v : integer);
      function    find_set(v : integer)
                             : integer;
      procedure   union_sets(e : Edge);
  end;

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

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

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

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

// Destruktor
//-----------
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 ustawiamy na koniec kopca
  i := hpos;
  // W kopcu będzie
  // o 1 element wiecej
  inc(hpos);
  // Obliczamy pozycję rodzica
  j := (i-1) Shr 1;
  // 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;
  // Krawędź e wstawiamy do kopca
  Heap[i] := e;
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
  // Tworzymy tablicę
  // dla elementów zbiorów
  SetLength(Z, n);
end;

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

// Tworzy wpis w tablicy Z
//------------------------
procedure DSStruct.make_set(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.find_set(v : integer)
                             : integer;
begin
  if Z[v].up <> v then
    Z[v].up := find_set(Z[v].up);
  find_set := Z[v].up;
end;

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

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

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

// Destruktor
//-----------
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
      // Zapamiętujemy wskazanie
      r := p;
      // Przesuwamy się do następnego
      // elementu listy
      p := p^.next;
      // Usuwamy element
      dispose(r);
    end;
  end;
  // Usuwamy tablicę list sąsiedztwa
  SetLength(A, 0);
end;

// Dodaje krawędź do drzewa
//-------------------------
procedure MSTree.addEdge(e : Edge);
var
  p : PTnode;
begin
  // Do wagi drzewa
  // dodajemy wagę krawędzi
  inc(weight, e.weight);
  // Tworzymy nowy węzeł
  new(p);
  // Wierzchołek końcowy
  p^.v := e.v2;
  // Waga krawędzi
  p^.weight := e.weight;
  // Dodajemy p do listy
  // wierzchołka v1
  p^.next := A[e.v1];
  A[e.v1] := p;
  // To samo dla
  // krawędzi odwrotnej
  new(p);
  // Wierzchołek końcowy
  p^.v := e.v1;
  // Waga krawędzi
  p^.weight := e.weight;
  // Dodajemy p do
  // listy wierzchołka v2
  p^.next := A[e.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('MSTree Weight = ', weight);
  writeln;
end;

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

var
  // Liczba wierzchołków i krawędzi
  n, m : integer;
  e : Edge;
  i : integer;
  // Struktura zbiorów rozłącznych
  Z : DSStruct;
  // Kolejka priorytetowa
  // oparta na kopcu
  Q : Queue;
  // Minimalne drzewo rozpinające
  T : MSTree;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Inicjujemy strukturę
  // zbiorów rozłącznych
  Z.init(n);
  // Inicjujemy kolejkę priorytetową
  Q.init(m);
  // Inicjujemy minimalne
  // drzewo rozpinające
  T.init(n);
  for i := 0 to n-1 do
    // Dla każdego wierzchołka
    // tworzymy osobny zbiór
    Z.make_set(i);
  for i := 1 to m do
  begin
    // Odczytujemy kolejne
    // krawędzie grafu
    read(e.v1, e.v2, e.weight);
    // i umieszczamy je
    // w kolejce priorytetowej
    Q.push(e);
  end;
  for i := 1 to n-1 do
  begin
    repeat
      // Pobieramy z kolejki krawędź
      e := Q.front;
      // Krawędź usuwamy z kolejki
      Q.pop;
    until Z.find_set(e.v1) <>
          Z.find_set(e.v2);
    // Dodajemy krawędź do drzewa
    T.addEdge(e);
    // Zbiory z wierzchołkami
    // łączymy ze sobą
    Z.union_sets(e);
  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
{
  // Wierzchołki krawędzi,
  // waga krawędzi
  int v1, v2, weight;
};

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 make_set(int v);
    int find_set(int v);
    void union_sets(Edge e);
};

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

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

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

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

// Destruktor
//-----------
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 ustawiamy na koniec kopca
  i = hpos++;
  // Obliczamy pozycję rodzica
  j = (i-1) >> 1;
  // Szukamy miejsca w kopcu dla e
  while(i && (Heap[j].weight > e.weight))
  {
    Heap[i] = Heap[j];
    i = j;
    j = (i-1) >> 1;
  }
  // Krawędź e wstawiamy do kopca
  Heap[i] = e;
}

// 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)
{
  // Tworzymy tablicę
  // dla elementów zbiorów
  Z = new DSNode[n];
}

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

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

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

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

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

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

// Konstruktor
//------------
MSTree::MSTree(int n)
{
  int i;

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

// Destruktor
//-----------
MSTree::~MSTree()
{
  int i;
  Tnode *p, *r;

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

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

  // Do wagi drzewa
  // dodajemy wagę krawędzi
  weight += e.weight;
  // Tworzymy nowy węzeł
  p = new Tnode;
  // Wierzchołek końcowy
  p->v = e.v2;
  // Waga krawędzi
  p->weight = e.weight;
  // Dodajemy p do listy
  // wierzchołka v1
  p->next = A[e.v1];
  A[e.v1] = p;
  // To samo dla
  // krawędzi odwrotnej
  p = new Tnode;
  // Wierzchołek końcowy
  p->v = e.v1;
  // Waga krawędzi
  p->weight = e.weight;
  // Dodajemy p do listy
  // wierzchołka v2
  p->next = A[e.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
       << "MST Weight = " << weight
       << endl << endl;
}

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

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

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

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

  for(i = 0; i < n; i++)
    // Dla każdego wierzchołka
    // tworzymy osobny zbiór
    Z.make_set(i);
  for(i = 0; i < m; i++)
  {
    // Odczytujemy kolejne
    // krawędzie grafu
    cin >> e.v1
        >> e.v2
        >> e.weight;
    // i umieszczamy je
    // w kolejce priorytetowej
    Q.push(e);
  }
  // Pętla wykonuje się
  // n-1 razy !!!
  for(i = 1; i < n; i++)
  {
    do
    {
      // Pobieramy z kolejki krawędź
      e = Q.front();
      // Krawędź usuwamy z kolejki
      Q.pop();
    } while(Z.find_set(e.v1) ==
            Z.find_set(e.v2));
    // Dodajemy krawędź do drzewa
    T.addEdge(e);
    // Zbiory z wierzchołkami
    // łączymy ze sobą
    Z.union_sets(e);
  }
  // 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
  ' Wierzchołki krawędzi,
  ' waga krawędzi
  v1 As Integer
  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 _
      make_set(ByVal v As Integer)
    Declare Function _
      find_set(ByVal v As Integer) _
                       As Integer
    Declare Sub _
      union_sets(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:
    ' Tablica list sąsiedztwa
    A As Tnode Ptr Ptr
    ' Liczba komórek w tablicy
    Alen As Integer
    ' Waga całego drzewa
    weight As Integer
  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
'------------
Constructor Queue(ByVal n As Integer)
  ' Tworzymy tablicę
  Heap = New Edge [n]
  ' Pozycja w kopcu
  hpos = 0
End Constructor

' Destruktor
'-----------
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 ustawiamy na koniec kopca
  i = hpos
  hpos += 1
  ' Obliczamy pozycję rodzica
  j = (i-1) Shr 1
  ' 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
  ' Krawędź e wstawiamy do kopca
  Heap[i] = e
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)
  ' Tworzymy tablicę dla
  ' elementów zbiorów
  Z = New DSNode[n]
End Constructor

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

' Tworzy wpis w tablicy Z
'------------------------
Sub DSStruct.make_set(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.find_set(ByVal v As Integer) _
                          As Integer
  If Z[v].up <> v Then _
    Z[v].up = find_set(Z[v].up)
  return Z[v].up
End Function

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

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

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

' Konstruktor
'------------
Constructor MSTree(ByVal n As Integer)
  Dim As Integer i

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

' Destruktor
'-----------
Destructor MSTree
  Dim As Integer i
  Dim As Tnode Ptr p, r

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

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

  ' Do wagi drzewa dodajemy
  ' wagę krawędzi
  weight += e.weight
  ' Tworzymy nowy węzeł
  p = New Tnode
  ' Wierzchołek końcowy
  p->v = e.v2
  ' Waga krawędzi
  p->weight = e.weight
  ' Dodajemy p do listy
  ' wierzchołka v1
  p->next = A[e.v1]
  A[e.v1] = p
  ' To samo dla krawędzi odwrotnej
  p = New Tnode
  ' Wierzchołek końcowy
  p->v = e.v1
  ' Waga krawędzi
  p->weight = e.weight
  ' Dodajemy p do listy
  ' wierzchołka v2
  p->next = A[e.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 "MST Weight =";weight
  Print
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków
' i krawędzi
Input #1, n, m
' Struktura zbiorów rozłącznych
Dim As DSStruct Z = n
' Kolejka priorytetowa
' oparta na kopcu
Dim As Queue Q = m
' Minimalne drzewo rozpinające
Dim As MSTree T = n
For i = 0 To n-1
  ' Dla każdego wierzchołka
  ' tworzymy osobny zbiór
  Z.make_set(i)
Next
For i = 1 To m
  ' Odczytujemy kolejne
  ' krawędzie grafu
  Input #1, e.v1, e.v2, e.weight
  'i umieszczamy je
  ' w kolejce priorytetowej
  Q.push(e)
Next
Close #1
' Pętla wykonuje się n-1 razy !!!
For i = 1 To n-1
  Do
    ' Pobieramy z kolejki krawędź
    e = Q.front
    ' Krawędź usuwamy z kolejki
    Q.pop
  Loop While Z.find_set(e.v1) = _
             Z.find_set(e.v2)
  ' Dodajemy krawędź do drzewa
  T.addEdge(e)
  ' Zbiory z wierzchołkami
  ' łączymy ze sobą
  Z.union_sets(e)
Next
' Wyświetlamy wyniki
T.Tprint
End

# Minimalne drzewo rozpinające
# Algorytm Kruskala
# Data: 8.03.2025
# (C)2025 mgr Jerzy Wałaszek
#------------------------------

# Definicje obiektów
#-------------------

# krawędź
class Edge:
    def __init__(self):
        # wierzchołki krawędzi,
        # waga krawędzi
        self.v1 = 0
        self.v2 = 0
        self.weight = 0


# kolejka
class Queue:
    # Konstruktor
    def __init__(self,n):
        # Tworzymy tablicę
        self.heap = [Edge() for i in range(n)]
        # Pozycja w kopcu
        self.hpos = 0


    # Destruktor
    def __del__(self):
        del self.heap


    # Zwraca krawędź z początku kopca
    def front(self):
        return self.heap[0]


    # Umieszcza w kopcu nową krawędź
    # i odtwarza strukturę kopca
    def push(self,e):
        # i ustawiamy na koniec kopca
        i = self.hpos
        self.hpos += 1
        # Obliczamy pozycję rodzica
        j = (i-1) >> 1
        # Szukamy miejsca w kopcu dla e
        while i and self.heap[j].weight > e.weight:
            self.heap[i] = self.heap[j]
            i = j
            j = (i-1) >> 1
        # Krawędź e wstawiamy do kopca
        self.heap[i] = e


    # Usuwa korzeń z kopca
    # i odtwarza jego strukturę
    def pop(self):
        if self.hpos:
            self.hpos -= 1
            e = self.heap[self.hpos]
            i = 0
            j = 1
            while j < self.hpos:
                if (j+1 < self.hpos) and \
                   (self.heap[j+1].weight <
                    self.heap[j].weight): j += 1
                if e.weight <= self.heap[j].weight:
                    break
                self.heap[i] = self.heap[j]
                i = j
                j = (j << 1) + 1
            self.heap[i] = e

# Definicje obiektu struktury
# zbiorów rozłącznych
class DSNode:
    def __init__(self):
        self.up = 0
        self.rank = 0


class DSStruct:
    # Konstruktor
    def __init__(self,n):
        # Tworzymy tablicę dla elementów zbiorów
        self.z = [DSNode() for i in range(n)]


    # Destruktor
    def __del__(self):
        # Usuwamy tablicę ze zbiorami
        del self.z


    # Tworzy wpis w tablicy Z
    def make_set(self,v):
        self.z[v].up = v
        self.z[v].rank = 0


    # Zwraca indeks reprezentanta zbioru,
    # w którym jest wierzchołek v
    def find_set(self,v):
        if self.z[v].up != v:
            self.z[v].up = self.find_set(self.z[v].up)
        return self.z[v].up


    # Łączy ze sobą zbiory z v i u
    def union_sets(self,e):
        # Wyznaczamy korzeń drzewa z węzłem u
        ru = self.find_set(e.v1)
        # Wyznaczamy korzeń drzewa z węzłem v
        rv = self.find_set(e.v2)
        # Korzenie muszą być różne
        if ru != rv:
            # Porównujemy rangi drzew
            if self.z[ru].rank > self.z[rv].rank:
                # ru większe, dołączamy rv
                self.z[rv].up = ru
            else:
                # równe lub rv większe, dołączamy ru
                self.z[ru].up = rv
                if self.z[ru].rank == self.z[rv].rank:
                    self.z[rv].rank += 1


# Definicje obiektu minimalnego
# drzewa rozpinającego

class Tnode:
    def __init__(self):
        self.next = None
        self.v = 0
        self.weight = 0


class MSTree:
    # Konstruktor
    def __init__(self,n):
        # Tworzymy tablicę dynamiczną
        self.a = [None] * n
        # Zapamiętujemy długość tablicy
        self.alen = n-1
        # Zerujemy wagę drzewa
        self.weight = 0


    # Destruktor
    def __del__(self):
        del self.a


    # Dodaje krawędź do drzewa
    def add_edge(self,e):
        # Do wagi drzewa dodajemy wagę krawędzi
        self.weight += e.weight
        # Tworzymy nowy węzeł
        p = Tnode()
        # Wierzchołek końcowy
        p.v = e.v2
        # Waga krawędzi
        p.weight = e.weight
        # Dodajemy p do listy wierzchołka v1
        p.next = self.a[e.v1]
        self.a[e.v1] = p
        # To samo dla krawędzi odwrotnej
        p = Tnode()
        # Wierzchołek końcowy
        p.v = e.v1
        # Waga krawędzi
        p.weight = e.weight
        # Dodajemy p do listy wierzchołka v2
        p.next = self.a[e.v2]
        self.a[e.v2] = p


    # Wyświetla zawartość drzewa
    # oraz jego wagę
    def t_print(self):
        print()
        for i in range(self.alen+1):
            print("Vertex ",i,"-",sep="",end="")
            p = self.a[i]
            while p:
                print(p.v,":",p.weight," ",
                      sep="",end="")
                p = p.next
            print()
        print()
        print("MST Weight =",self.weight)
        print()


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Struktura zbiorów rozłącznych
z = DSStruct(n)
# Kolejka priorytetowa oparta na kopcu
q = Queue(m)
# Minimalne drzewo rozpinające
t = MSTree(n)
for i in range(n):
    # Dla każdego wierzchołka
    # tworzymy osobny zbiór
    z.make_set(i)
for i in range(m):
    # Odczytujemy kolejne krawędzie grafu
    e = Edge()
    x = input().split()
    e.v1 = int(x[0])
    e.v2 = int(x[1])
    e.weight = int(x[2])
    # i umieszczamy je w kolejce priorytetowej
    q.push(e)
# Pętla wykonuje się n-1 razy !!!
for i in range(1, n):
    while True:
        # Pobieramy z kolejki krawędź
        e = q.front()
        # Krawędź usuwamy z kolejki
        q.pop()
        if z.find_set(e.v1) != z.find_set(e.v2):
            break
    # Dodajemy krawędź do drzewa
    t.add_edge(e)
    # Zbiory z wierzchołkami łączymy ze sobą
    z.union_sets(e)
# Wyświetlamy wyniki
t.t_print()

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

// Definicja obiektu kolejki
// priorytetowej
//--------------------------
type
  Edge = record
    // Wierzchołki krawędzi
    v1,v2 : integer;
    // Waga krawędzi
    weight : integer;
  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
      // Tablica
      // list sąsiedztwa
      A : array of PTnode;
      // Liczba komórek
      // w tablicy
      Alen : integer;
      // Waga całego drzewa
      weight : integer;
    public
      constructor
        init(n : integer);
      destructor destroy;
      procedure
        addEdge(e : Edge);
      function
        getAList(n : integer)
                   : PTnode;
      procedure print;
  end;

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

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

// Destruktor
//-----------
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 ustawiamy
  // na koniec kopca
  i := hpos;
  // W kopcu będzie
  // o 1 element wiecej
  inc(hpos);
  // Obliczamy pozycję rodzica
  j := (i-1) Shr 1;
  // 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;
  // Krawędź e
  // wstawiamy do kopca
  Heap[i] := e;
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
//------------
constructor
  MSTree.init(n : integer);
var
  i : integer;
begin
  // Tworzymy
  // tablicę dynamiczną
  SetLength(A, n);
  // i wypełniamy ją
  // pustymi listami
  for i := 0 to n-1 do
    A[i] := nil;
  // Zapamiętujemy
  // długość tablicy
  Alen := n-1;
  // Zerujemy wagę drzewa
  weight := 0;
end;

// Destruktor
//-----------
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
      // Zapamiętujemy
      // wskazanie
      r := p;
      // Przesuwamy się
      // do następnego
      // elementu listy
      p := p^.next;
      // Usuwamy element
      dispose(r);
    end;
  end;
  // Usuwamy tablicę
  // list sąsiedztwa
  SetLength(A, 0);
end;

// Dodaje krawędź do drzewa
//-------------------------
procedure
  MSTree.addEdge(e : Edge);
var
  p : PTnode;
begin
  // Do wagi drzewa dodajemy
  // wagę krawędzi
  inc(weight, e.weight);
  // Tworzymy nowy węzeł
  new(p);
  // Wierzchołek końcowy
  p^.v := e.v2;
  // Waga krawędzi
  p^.weight := e.weight;
  // Dodajemy p do listy
  // wierzchołka v1
  p^.next := A[e.v1];
  A[e.v1] := p;
  // To samo dla
  // krawędzi odwrotnej
  new(p);
  // Wierzchołek końcowy
  p^.v := e.v1;
  // Waga krawędzi
  p^.weight := e.weight;
  // Dodajemy p do listy
  // wierzchołka v2
  p^.next := A[e.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('MST Weight = ',
          weight);
  writeln;
end;

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

var
  // Liczba wierzchołków
  // i krawędzi
  n, m : integer;
  e : Edge;
  p : PTnode;
  i, v : integer;
  // Kolejka priorytetowa
  // oparta na kopcu
  Q : Queue;
  // Graf
  G : MSTree;
  // Minimalne drzewo
  // rozpinające
  T : MSTree;
  // Tablica odwiedzin
  vs : array of boolean;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Inicjujemy kolejkę
  // priorytetową
  Q.init(m);
  // Inicjujemy minimalne
  // drzewo rozpinające
  T.init(n);
  // Inicjujemy graf
  G.init(n);
  // Tworzymy tablicę
  // odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // Inicjujemy tablicę
    // odwiedzin
    vs[i] := false;
  for i := 1 to m do
  begin
    // Odczytujemy kolejne
    // krawędzie grafu
    read(e.v1, e.v2, e.weight);
    // i umieszczamy je w G
    G.addEdge(e);
  end;
  // Tworzymy minimalne
  // drzewo rozpinające
  //-------------------
  // Wierzchołek startowy
  v := 0;
  // Oznaczamy go
  // jako odwiedzonego
  vs[v] := true;
  // Do drzewa dodamy
  // n-1 krawędzi grafu
  for i := 1 to n-1 do
  begin
    // Pobieramy adres
    // listy sąsiadów do p
    p := G.getAList(v);
    // Przeglądamy listę
    while p <> nil do
    begin
      if not vs[p^.v] then
      begin
        // Tworzymy krawędź
        e.v1 := v;
        e.v2 := p^.v;
        e.weight := p^.weight;
        // Dodajemy ją do
        // kolejki
        // priorytetowej
        Q.push(e);
      end;
      // Następny sąsiad
      p := p^.next;
    end;
    repeat
      // Pobieramy krawędź
      // z kolejki
      e := Q.front;
      Q.pop;
    // Krawędź prowadzi
    // poza drzewo?
    until not vs[e.v2];
    // Dodajemy krawędź
    // do drzewa rozpinającego
    T.addEdge(e);
    // Oznaczamy drugi
    // wierzchołek
    // jako odwiedzony
    vs[e.v2] := true;
    v := e.v2;
  end;
  // Wyświetlamy wyniki
  T.print;
  // Usuwamy struktury
  Q.destroy;
  T.destroy;
  G.destroy;
  SetLength(vs, 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
{
  // Wierzchołki krawędzi,
  // waga krawędzi
  int v1, v2, weight;
};

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:
    // Tablica list sąsiedztwa
    Tnode ** A;
    // Liczba komórek w tablicy
    int Alen;
    // Waga całego drzewa
    int weight;
  public:
    MSTree(int n);
    ~MSTree();
    void addEdge(Edge e);
    Tnode * getAList(int n);
    void print();
};

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

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

// Destruktor
//-----------
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 ustawiamy
  // na koniec kopca
  i = hpos++;
  // Obliczamy pozycję
  // rodzica
  j = (i-1) >> 1;
  // Szukamy miejsca
  // w kopcu dla e

  while(i &&
        (Heap[j].weight >
         e.weight))
  {
    Heap[i] = Heap[j];
    i = j;
    j = (i-1) >> 1;
  }
  // Krawędź e
  // wstawiamy do kopca
  Heap[i] = e;
}

// 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
//------------
MSTree::MSTree(int n)
{
  int i;

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

// Destruktor
//-----------
MSTree::~MSTree()
{
  int i;
  Tnode *p, *r;

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

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

  // Do wagi drzewa dodajemy
  // wagę krawędzi
  weight += e.weight;
  // Tworzymy nowy węzeł
  p = new Tnode;
  // Wierzchołek końcowy
  p->v = e.v2;
  // Waga krawędzi
  p->weight = e.weight;
  // Dodajemy p do listy
  // wierzchołka v1
  p->next = A[e.v1];
  A[e.v1] = p;
  // To samo dla
  // krawędzi odwrotnej
  p = new Tnode;
  // Wierzchołek końcowy
  p->v = e.v1;
  // Waga krawędzi
  p->weight = e.weight;
  // Dodajemy p do
  // listy wierzchołka v2
  p->next = A[e.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
       << "MST Weight = "
       << weight
       << endl << endl;
}

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Kolejka priorytetowa
  //  oparta na kopcu
  Queue Q(m);
  // Minimalne
  // drzewo rozpinające
  MSTree T(n);
  // Graf
  MSTree G(n);
  bool * vs = new bool [n];

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

  for(i = 0; i < m; i++)
  {
    // Odczytujemy kolejne
    // krawędzie grafu
    cin >> e.v1
        >> e.v2
        >> e.weight;
    // i umieszczamy je w G
    G.addEdge(e);
  }
  // Tworzymy minimalne
  // drzewo rozpinające
  //-------------------
  // Wierzchołek startowy
  v = 0;
  // Oznaczamy go
  // jako odwiedzonego
  vs[v] = true;

  // Do drzewa dodamy
  // n-1 krawędzi grafu
  for(i = 1; i < n; i++)
  {
    // Przeglądamy
    // listę sąsiadów
    for(p = G.getAList(v);
        p; p = p->next)
      // Jeśli sąsiad
      // jest nieodwiedzony,
      if(!vs[p->v])
      {
        // to tworzymy krawędź
        e.v1 = v;
        e.v2 = p->v;
        e.weight = p->weight;
        // Dodajemy ją do
        // kolejki
        // priorytetowej
        Q.push(e);
      }
    do
    {
      // Pobieramy krawędź
      // z kolejki
      e = Q.front();
      Q.pop();
    // Krawędź prowadzi
    // poza drzewo?
    } while(vs[e.v2]);
    // Dodajemy krawędź
    // do drzewa rozpinającego
    T.addEdge(e);
    // Oznaczamy drugi
    // wierzchołek jako
    // odwiedzony
    vs[e.v2] = true;
    v = e.v2;
  }
  // Wyświetlamy wyniki
  T.print();
  delete [] vs;
  return 0;
}

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

' Definicja obiektu
' kolejki priorytetowej
'---------------------
Type Edge
  ' Wierzchołki krawędzi, waga krawędzi
  v1 As Integer
  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:
    ' Tablica list sąsiedztwa
    A As Tnode Ptr Ptr
    ' Liczba komórek w tablicy
    Alen As Integer
    ' Waga całego drzewa
    weight As Integer
  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 print_t
End Type

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

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

' Destruktor
'-----------
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 ustawiamy na koniec kopca
  i = hpos
  hpos += 1
  ' Obliczamy pozycję rodzica
  j = (i-1) Shr 1
  ' 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
  ' Krawędź e wstawiamy do kopca
  Heap[i] = e
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
'------------
Constructor MSTree(ByVal n As Integer)
  Dim As Integer i

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

' Destruktor
'-----------
Destructor MSTree()
  Dim As Integer i
  Dim As Tnode Ptr p, r

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

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

  ' Do wagi drzewa dodajemy wagę krawędzi
  weight += e.weight
  ' Tworzymy nowy węzeł
  p = New Tnode
  ' Wierzchołek końcowy
  p->v = e.v2
  ' Waga krawędzi
  p->weight = e.weight
  ' Dodajemy p do listy wierzchołka v1
  p->next = A[e.v1]
  A[e.v1] = p
  ' To samo dla krawędzi odwrotnej
  p = New Tnode
  ' Wierzchołek końcowy
  p->v = e.v1
  ' Waga krawędzi
  p->weight = e.weight
  ' Dodajemy p do listy wierzchołka v2
  p->next = A[e.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.print_t
  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 "MST Weight =";weight
  Print
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Kolejka priorytetowa oparta na kopcu
Dim As Queue Q = m
' Minimalne drzewo rozpinające
Dim As MSTree T = n
' Graf
Dim As MSTree G = n
Dim As Byte vs(0 To N-1)
For i = 0 To n-1
  ' Inicjujemy tablicę odwiedzin
  vs(i) = 0
Next
For i = 1 To m
  ' Odczytujemy kolejne krawędzie grafu
  Input #1, e.v1, e.v2, e.weight
  ' i umieszczamy je w G
  G.addEdge(e)
Next
Close #1
' Tworzymy minimalne drzewo rozpinające
'--------------------------------------
' Wierzchołek startowy
v = 0
' Oznaczamy go jako odwiedzonego
vs(v) = 1
' Do drzewa dodamy n-1 krawędzi grafu
For i = 2 To n
  ' Przeglądamy listę sąsiadów
  p = G.getAList(v)
  While p
    ' Jeśli sąsiad jest nieodwiedzony,
    If vs(p->v) = 0 Then
      ' to tworzymy krawędź
      e.v1 = v
      e.v2 = p->v
      e.weight = p->weight
      ' Dodajemy ją
      ' do kolejki priorytetowej
      Q.push(e)
    End If
    ' Następny sąsiad
    p = p->Next
  Wend
  Do
    ' Pobieramy krawędź z kolejki
    e = Q.front
    Q.pop
  ' Krawędź prowadzi poza drzewo?
  Loop While vs(e.v2) = 1
  ' Dodajemy krawędź
  ' do drzewa rozpinającego
  T.addEdge(e)
  ' Oznaczamy drugi
  ' wierzchołek jako odwiedzony
  vs(e.v2) = 1
  v = e.v2
Next
' Wyświetlamy wyniki
T.print_t
End

# Minimalne drzewo rozpinające
# Algorytm Prima
# Data: 11.03.2025
# (C)2025 mgr Jerzy Wałaszek
#-----------------------------

# Definicja obiektu
# kolejki priorytetowej
class Edge:
    def __init__(self):
        # Wierzchołki krawędzi,
        # waga krawędzi
        self.v1 = 0
        self.v2 = 0
        self.weight = 0


class Queue:
    # Konstruktor
    def __init__(self,n):
        # Tworzymy tablicę
        self.heap = [None] * n
        # Pozycja w kopcu
        self.hpos = 0


    # Destruktor
    def __del__(self):
        del self.heap


    # Zwraca krawędź z początku kopca
    def front(self):
        return self.heap[0]


    # Umieszcza w kopcu nową krawędź
    # i odtwarza strukturę kopca
    def push(self,e):
        # i ustawiamy na koniec kopca
        i = self.hpos
        self.hpos += 1
        # Obliczamy pozycję rodzica
        j = (i-1) >> 1
        # Szukamy miejsca w kopcu dla e
        while i and \
              self.heap[j].weight > e.weight:
            self.heap[i] = self.heap[j]
            i = j
            j = (i-1) >> 1
        # Krawędź e wstawiamy do kopca
        self.heap[i] = e


    # Usuwa korzeń z kopca
    # i odtwarza jego strukturę
    def pop(self):
        if self.hpos:
            self.hpos -= 1
            e = self.heap[self.hpos]
            i = 0
            j = 1
            while j < self.hpos:
                if (j+1 < self.hpos) and \
                   (self.heap[j+1].weight <
                    self.heap[j].weight):
                    j += 1
                if e.weight <= self.heap[j].weight:
                    break
                self.heap[i] = self.heap[j]
                i = j
                j = (j << 1)+1
            self.heap[i] = e


class Tnode:
    def __init__(self):
        self.next = None
        self.v = 0
        self.weight = 0


class MSTree:
    # Konstruktor
    def __init__(self,n):
        # Tworzymy tablicę dynamiczną
        self.a = [None] * n
        # Zapamiętujemy długość tablicy
        self.alen = n-1
        # Zerujemy wagę drzewa
        self.weight = 0


    # Destruktor
    def __del__(self):
        for i in range(self.alen):
            while self.a[i]:
                self.a[i] = self.a[i].next
        # Usuwamy tablicę list sąsiedztwa
        del self.a


    # Dodaje krawędź do drzewa
    def add_edge(self,e):
        # Do wagi drzewa dodajemy
        # wagę krawędzi
        self.weight += e.weight
        # Tworzymy nowy węzeł
        p = Tnode()
        # Wierzchołek końcowy
        p.v = e.v2
        # Waga krawędzi
        p.weight = e.weight
        # Dodajemy p do listy wierzchołka v1
        p.next = self.a[e.v1]
        self.a[e.v1] = p
        # To samo dla krawędzi odwrotnej
        p = Tnode()
        # Wierzchołek końcowy
        p.v = e.v1
        # Waga krawędzi
        p.weight = e.weight
        # Dodajemy p do listy wierzchołka v2
        p.next = self.a[e.v2]
        self.a[e.v2] = p


    # Zwraca wskaźnik początku
    # listy sąsiadów wierzchołka
    def get_alist(self,n):
        return self.a[n]


    # Wyświetla zawartość
    # drzewa oraz jego wagę
    def print_t(self):
        print()
        for i in range(self.alen+1):
            print("Vertex ",i,"-",sep="",end="")
            p = self.a[i]
            while p:
                print("%d:%d" % (p.v,p.weight),
                      end=" ")
                p = p.next
            print()
        print()
        print("MST Weight =",self.weight)
        print()


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Kolejka priorytetowa oparta na kopcu
q = Queue(m)
# Minimalne drzewo rozpinające
t = MSTree(n)
# Graf
g = MSTree(n)
vs = [False] * n
for i in range(m):
    # Odczytujemy kolejne krawędzie grafu
    x = input().split()
    e = Edge()
    e.v1 = int(x[0])
    e.v2 = int(x[1])
    e.weight = int(x[2])
    # i umieszczamy je w G
    g.add_edge(e)
# Tworzymy minimalne drzewo rozpinające
#--------------------------------------
# Wierzchołek startowy
v = 0
# Oznaczamy go jako odwiedzonego
vs[v] = True
# Do drzewa dodamy n-1 krawędzi grafu
for i in range(2, n+1):
    # Przeglądamy listę sąsiadów
    p = g.get_alist(v)
    while p:
        # Jeśli sąsiad jest nieodwiedzony,
        if not vs[p.v]:
            # to tworzymy krawędź
            e = Edge()
            e.v1 = v
            e.v2 = p.v
            e.weight = p.weight
            # Dodajemy ją
            # do kolejki priorytetowej
            q.push(e)
        # Następny sąsiad
        p = p.next
    while True:
        # Pobieramy krawędź z kolejki
        e = q.front()
        q.pop()
        # Krawędź prowadzi poza drzewo?
        if not vs[e.v2]: break
    # Dodajemy krawędź
    # do drzewa rozpinającego
    t.add_edge(e)
    # Oznaczamy drugi
    # wierzchołek jako odwiedzony
    vs[e.v2] = True
    v = e.v2
# Wyświetlamy wyniki
t.print_t()