#include
using namespace std;


struct KrawedzGrafu{
int odwezla;
int dowezla;
int koszt;


};

// typedef KrawedzGrafu Graf[ MaxIloscKrawedzi ];




void SortujKrawedzie( KrawedzGrafu **G1, int gk)
{

KrawedzGrafu tmp;

for (int i=1; i<= gk-1; i++)
for (int j=1; j<= gk-i; j++)
if ( (*G1)[j].koszt > (*G1)[j+1].koszt )
{
tmp = (*G1)[j];
(*G1)[j] = (*G1)[j+1];
(*G1)[j+1] = tmp;
}
}


int AlgKruskala( int n, KrawedzGrafu **G1, KrawedzGrafu **T1 )
{
//int Z[ MaxIloscWezlow ];
int *Z = (int*)malloc( sizeof( int) * (n+3) );
int j, k, u, v, w;
int tk =0;

for (int i=1; i<=n; i++) Z[i] = 0;

//(*tk) =0;
k =1;

j =1;
while (k {
u = (*G1)[j].odwezla;
v = (*G1)[j].dowezla;
j =j+1;
if ( Z[u]==0 || Z[v]==0 || Z[u]!=Z[v] )
{
tk =tk +1;
(*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[])
{

// Graf S, C;

int n, gk, tk;

cout <<""< cout << " WITAJ!!! " < cout <<""< cout << " TO JEST PROGRAM KTORY WYZNACZA MINIMALNE DRZEWO ROZPINAJACE GRAFU SKIEROWANEGO" < cout <<""< cout <<""< cout <<"Podaj Ilosc Wezlow: ";
cin >> n;
cout <<"Podaj Ilosc Krawedzi: ";
cin >> gk;
cout<<""< cout <<"OdWezla DoWezla Koszt\n";
cout <<""<
KrawedzGrafu *S = (KrawedzGrafu *)malloc( (gk+3)* sizeof( KrawedzGrafu ) );
KrawedzGrafu *C = (KrawedzGrafu *)malloc( (gk+3)* sizeof( KrawedzGrafu ) );

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


SortujKrawedzie( &S, gk);

tk = AlgKruskala(n, &S, &C );

for ( int i=1; i<= tk; i++)
{
cout < " << C[i].dowezla << " : " << C[i].koszt << '\n';
cout.flush();
}

delete S;
delete C;

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

return 0;

}