#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
        int x,y,c;
        };
muchie v[200001],sol[200001];

int n,m,t[200001];

void read()
{       int i;
        fin>>n>>m;
        for(i=1;i<=m;i++)
                fin>>v[i].x>>v[i].y>>v[i].c;
}

int cmp(muchie a, muchie b)
{       return a.c<b.c;}
void kruskal()
{       int i,j,k,l,nr,ct=0,ind=0;
        for(i=1;i<=n;i++) t[i]=i;
        i=1;
        nr=0;
        while(nr<n-1)
        {       if(t[v[i].x]!=t[v[i].y])
                {       nr++;
                        ct+=v[i].c;
                        sol[++ind]=v[i];
                        k=t[v[i].x];
                        l=t[v[i].y];
                        for(j=1;j<=n;j++)
                                if(t[j]==k) t[j]=l;
                }
                i++;
        }
        fout<<ct<<'\n'<<n-1<<'\n';
        for(i=1;i<=ind;i++)
                fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}

int main()
{       read();
        sort(v+1,v+1+m,cmp);
        kruskal();
        return 0;
}