#include <iostream>
#include <fstream>
#include <utility>
#include <set>
#include <vector>
#include <algorithm>


using namespace std;
struct comp3
{
    bool operator()(vector<int> a,vector<int> b)
    {
        if(a[0]<b[0])
            return true;
        return false;
    }
}c3;
bool com(vector<int> a,vector<int> b)
    {
        if(a[0]==b[0])
            return true;
        return false;
    }
struct comp{
bool operator () (pair<vector<int>,int> a,pair<vector<int>,int> b)
{
    //ordoneaza mai intai dupa ponderi
    if(a.second<b.second)
        return true;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            if(a.first[i]<b.first[i])
                return true;
    return false;
}
};
struct comp2{
bool operator () (pair<vector<int>,int> a,pair<vector<int>,int> b)
{
    //ordoneaza mai intai dupa nod
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            if(a.first[i]<b.first[i])
                return true;
    if(a.second<b.second)
        return true;
    return false;
}
};
class gf
{
    int n; //nr vf
    set<pair<vector<int>,int>, comp>E; //muchiile
    public:
    gf():n(0)
    {
    }
    gf(gf &m)
    {
        n=m.n;
        E=m.E;
    }
friend ostream &operator <<(ostream &,const gf &);
friend istream &operator >>(istream &,gf &);
friend class arbore_prim;
friend class arbore_kruskal;
};
istream &operator >> (istream &in,gf &m)
{
    vector<int> v;
    in>>m.n;
    int p,a,b,c;
    in>>p;
    while(p)
    {
        p--;
        in>>a;
        v.push_back(a);
        in>>b>>c;
        v.push_back(b);
        m.E.insert(make_pair(v,c));
        v.clear();
    }
}

ostream &operator <<(ostream & out,const gf &m)
{
    for(set<pair<vector<int>,int> >::iterator j=m.E.begin();j!=m.E.end();j++)
        out<<(*j).first[0]<<" "<<(*j).first[1]<<" "<<(*j).second<<endl;
}

class arbore_kruskal
{
    int n;
    int suma;
    set<pair<int,int> > m;
public:
    arbore_kruskal():n(0){}
    arbore_kruskal(int noduri, set<pair<int, int> >muchii):n(noduri),m(muchii){};
    arbore_kruskal(arbore_kruskal &A){n=A.n; m=A.m;}
    arbore_kruskal kruskal(gf G);
    int reuniune(vector<int> &a,int u, int v);
    int gaseste(vector<int> &a,int i,int &h);
    friend ostream &operator <<(ostream &,const arbore_kruskal &);
};
ostream &operator <<(ostream & out,const arbore_kruskal &a)
{
    out<<a.suma<<endl;
    out<<a.m.size()<<endl;
    for(set<pair<int,int> >::iterator j=a.m.begin();j!=a.m.end();j++)
        out<<(*j).first<<"  "<<(*j).second<<endl;
}
arbore_kruskal arbore_kruskal::kruskal(gf g)
{
    cout<<"Kruskal"<<endl;
    arbore_kruskal a;
    int suma=0;
    vector<int> v; //creez cate un arbore distinct pentru fiecare varf
    for(int j=0;j<=g.n;j++)
    {
        v.push_back(-1);
    }
    int l,m;
    for(set<pair<vector<int>,int> >::iterator i=g.E.begin();i!=g.E.end();i++)
    {
        if(gaseste(v,(*i).first[0],l)!=gaseste(v,(*i).first[1],m))
        {
            a.n++;
            a.m.insert(make_pair((*i).first[0],(*i).first[1]));
            reuniune(v,(*i).first[0],(*i).first[1]);
            suma=suma+(*i).second;
            if(a.n==(g.n-1))
                i=g.E.end();
        }
    }

    a.suma=suma;
    return a;
}
int arbore_kruskal::gaseste(vector<int> &a,int i,int &h)
{
    h=0;//distanta de la nod la radacina
    int rad,var;
    for(rad=i;a[rad]!=-1;rad=a[rad]);
    for(;a[i]!=-1;)
    {
        h++;
        //compresia drumurilor
        var=a[i];
        a[i]=rad;
        i=var;

    }
    return rad;
}

int arbore_kruskal::reuniune(vector<int> &a,int u, int v)
{
    int h1,h2;
    u=gaseste(a,u,h1);
    v=gaseste(a,v,h2);
    if(h1>h2)
        a[v]=u;
    else
        a[u]=v;
    return 0;
}

int main()
{
    gf g;
    fstream in("apm.in",ios::in);
    in>>g;
    in.close();
    arbore_kruskal k;
    fstream out("apm.out",ios::out);
    out<<k.kruskal(g);
    return 0;
}