#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie{int x; int y; int c;}v[400001];

int cmp(muchie x,muchie y)
{
    return(x.c<y.c);
}
vector <int> B[400001];
int n,m,aux1,aux2,x,y,c;
int A[400001],sol,C[400001],w,D[400001];
int main()
{
    int i;
    FILE *f=fopen("apm.in","r");
    FILE *g=fopen("apm.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        v[i].x=x;v[i].y=y;v[i].c=c; //vectorul de muchii
        A[i]=i;//subarborele lui i este i
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)B[i].push_back(i);
    for(i=1;i<=m;i++)
        {
            x=v[i].x;y=v[i].y;
            if(A[x]!=A[y])
            {
                C[++w]=x;
                D[w]=y;
                sol+=v[i].c;
                aux1=A[x];
                aux2=A[y];
                while(!B[aux2].empty()){B[aux1].push_back(B[aux2].back());A[B[aux2].back()]=A[x];B[aux2].pop_back();}
            }
        }
        fprintf(g,"%d\n%d\n",sol,n-1);
        for(i=1;i<=w;i++)fprintf(g,"%d %d\n",D[i],C[i]);
        fclose(f);
        fclose(g);
    return 0;
}