#include<bits/stdc++.h>

using namespace std;

#define muchie pair<int,int>

class graf
{
    int n,m,x,y,c,px,py,costtotal=0;
    vector <pair <int,muchie> > G,MST;
    vector <int> parinti;
    int gasit(int x);
public:
    graf(char* filename);
    void mst();
};

graf::graf(char *filename)
{
    int i;
    ifstream f(filename);
    f>>n>>m;
    for(i=0;i<=n;i++)
        parinti.push_back(i);
    for(i=0;i<=m;i++)
    {
        f>>x>>y>>c;
        G.push_back(pair<int,muchie>(c,make_pair(x,y)));
    }

}

int graf::gasit(int x)
{
    if(x!=parinti[x])
        parinti[x]=gasit(parinti[x]);
    return parinti[x];
}

void graf::mst()
{

    sort(G.begin(),G.end());
    for(int i=0;i<m;i++)
    {
        px=gasit(G[i].second.first);
        py=gasit(G[i].second.second);
        if((px)!=(py))
        {

            MST.push_back(G[i]);
            costtotal+=G[i].first;
            parinti[px]=parinti[py];
        }
    }

    for(int i=0;i<MST.size();i++)
        cout<<"("<<MST[i].second.first<<" "<<MST[i].second.second<<" ) :"<<MST[i].first<<endl;
    cout<<"Costul minim total este :"<<costtotal<<endl;
}



int main()
{
    graf X("graf.txt");
    X.mst();
    return 0;
}