#include <bits/stdc++.h>
using namespace std;
struct coord{
int x,y,cost;
bool operator<(const coord & e)const {
return cost>e.cost;
}
}w;
priority_queue <coord> C;
struct muchie
{
    int i,j,cost;
};
ifstream f("kruskal.in");
ofstream g("kruskal.out");
int n,m,t[105],S,nr,cn;
muchie x[5005],v[5005];
bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        f>>w.x>>w.y>>w.cost;
        C.push(w);
    }
    //sort(x+1,x+m+1,cmp);
    for(int i=1; i<=n; ++i)t[i]=i;
    for(int i=0;i<m && nr<n;i++)
    {
        w=C.top();
        int l=w.x,c=w.y,val=w.cost;
        C.pop();
        if(t[l]!=t[c])
        {
            S+=val;
            v[++cn].i=l;v[cn].j=c;
            int ai=t[l],aj=t[c];
            for(int j=1;j<=n;++j)
                if(t[j]==aj)t[j]=ai;
        }
    }
    g<<S<<'\n'<<cn<<'\n';
    for(int i=1;i<=cn;i++)
    {
        g<<v[i].i<<" "<<v[i].j<<'\n';
    }
    return 0;
}