#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> C,D;
int n,m,aux1,aux2,x,y,c;
int A[200001],sol,w;
int T[200001],RG[200001];
void cauta(int x,int &rez)
{
    int aux=x;
    int z;
    while(T[x]!=x)x=T[x];
    while(T[aux]!=aux){z=T[aux];T[aux]=x;aux=z;}
    rez=x;
}

void uneste(int x,int y)
{
    int aux;
    int x1;cauta(x,x1);
    int y1;cauta(y,y1);
    if(RG[x1]==RG[y1]){T[y1]=x1;RG[x1]++;}
    else {if(x1>y1){aux=x1;x1=y1;y1=aux;}T[x1]=y1;}
}

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
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++){RG[i]=1;T[i]=i;}
    for(i=1;i<=m;i++)
        {
            x=v[i].x;y=v[i].y;
            cauta(x,aux1);cauta(y,aux2);
            if(aux1!=aux2)
            {
                D.push_back(x);
                C.push_back(y);
                sol+=v[i].c;
                uneste(x,y);
            }
        }
        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;
}