[pbInfo] kruskal

#include <fstream>
#include <algorithm>

using namespace std;

ofstream fout("kruskal.out");

int arbore[1001], x, y, cost, n, m, unific[101], ct;

struct muchie
{
    int x, y, cost;
}
a[1001];

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void CitireMuchii()
{
    ifstream fin("kruskal.in");
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        a[i].x = x; a[i].y = y;
        a[i].cost = cost;
    }
    fin.close();
}

void CreareArbore()
{
    int i = 1, k = 0, aux;
    for(int j = 1; j <= n; j++) unific[j]=j;
    while(k < n - 1)
    {
        if(unific[a[i].x] != unific[a[i].y])
        {
            ct = ct + a[i].cost;
            k++;
            arbore[k] = i;
            aux = unific[a[i].y];
            for(int j = 1; j <= n; j++)
                if(unific[j] == aux) unific[j] = unific[a[i].x];
        }
        i++;
    }
}

void AfisareMuchii()
{
    for(int i = 1; i <= n-1; i++)
        fout << a[arbore[i]].x << ' ' << a[arbore[i]].y << '\n';
}

int main()
{
    CitireMuchii();
    sort(a, a + m, cmp);
    CreareArbore();
    fout << ct << '\n';
    AfisareMuchii();
    fout.close();
    return 0;
}