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

using namespace std;

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

int cmp(muchie x,muchie y)
{
    return(x.c<y.c);
}
vector <int> B[200001],C,D;
int n,m,aux1,aux2,x,y,c;
int A[200001],sol,w;
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.push_back(x);
                D.push_back(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<=n-1;i++){fprintf(g,"%d %d\n",D.back(),C.back());D.pop_back();C.pop_back();}
        fclose(f);
        fclose(g);
    return 0;
}