#include
using namespace std;

template
void quicksort(T * const tablica, int const x, int const y)
{
int i = x, j = y;
T v = tablica[div(x + y, 2).quot], temp;
do
{
while (tablica[i] < v) ++i;
while (v < tablica[j]) --j;
if (i <= j)
{
temp = tablica[i];
tablica[i] = tablica[j];
tablica[j] = temp;
++i;
--j;
}
}
while (i <= j);
if (x < j) quicksort(tablica, x, j);
if (i < y) quicksort(tablica, i, y);
}

struct KrawedzGrafu
{
int odwezla;
int dowezla;
int koszt;
friend bool operator<= (KrawedzGrafu & k1, KrawedzGrafu & k2) {return k1.koszt <= k2.koszt;}
friend bool operator< (KrawedzGrafu & k1, KrawedzGrafu & k2) {return k1.koszt < k2.koszt;}
};

int algorytm_kruskala(int const n, KrawedzGrafu const * const G1, KrawedzGrafu * const T1)
{
int * Z = new int[n + 3];
for (int i = 1; i <= n; ++i) Z[i] = 0;
int j = 1, k = 1, u, v, w;
int tk = 0;
while (k < n)
{
u = G1[j].odwezla;
v = G1[j].dowezla;
++j;
if (Z[u] == 0 || Z[v] == 0 || Z[u] != Z[v])
{
++tk;
T1[tk] = G1[j - 1];
if (Z[u] == 0 && Z[v] != 0)
{
w = u;
u = v;
v = w;
}
if (Z[u] == 0) Z[u] = u;
if (Z[v] == 0) Z[v] = Z[u];
else
{
w = Z[v];
for (int i = 1; i <= n; ++i)
if (Z[i] == w)
Z[i] = Z[u];
}
k = k + 1;
}
}
delete Z;
return tk;
}

#include
#include

int main(int argc, char* argv[])
{
int n, wek, wyk;
cout << "Ilosc wezlow: ";
cin >> n;
cout << "Ilosc krawedzi: ";
cin >> wek;
cout << "OdWezla DoWezla Koszt\n";

KrawedzGrafu * We = new KrawedzGrafu[wek + 3];
KrawedzGrafu * Wy = new KrawedzGrafu[wek + 3];

for (int i = 1; i <= wek; ++i)
cin >> We[i].odwezla >> We[i].dowezla >> We[i].koszt;

quicksort(We, 1, wek);
wyk = algorytm_kruskala(n, We, Wy);

for (int i = 1; i <= wyk; ++i)
cout << Wy[i].odwezla << " -> " << Wy[i].dowezla << " : " << Wy[i].koszt << '\n';
cout.flush();

delete We;
delete Wy;

cin.ignore(numeric_limits::max(), '\n');
cin.get();

return 0;
}