#include <bits/stdc++.h>

#define MaxN 200005
#define INF 2140000000
#define MOD 1999999973

using namespace std;

FILE*IN,*OUT;

int N,M,out[MaxN],v[MaxN],Size=0,cost=0;
pair<int,int>Stack[MaxN];
struct spec
{
    int x,y,c;
}E[2*MaxN];
bool cond(spec a,spec b)
{
    return a.c<b.c;
}
int Find(int x)
{
    int y=x,t;
    while(v[y]!=y)
        y=v[y];
    while(x!=y)
    {
        t=v[x];
        v[x]=y;
        x=t;
    }
    return y;
}
void Unite(int x,int y)
{
    x=Find(x),y=Find(y);
    v[y]=x;
}
int main()
{
    IN=fopen("apm.in","r");
    OUT=fopen("apm.out","w");

    fscanf(IN,"%d%d",&N,&M);

    for(int i=1;i<=N;i++)
        v[i]=i;

    for(int i=1;i<=M;i++)
        fscanf(IN,"%d%d%d",&E[i].x,&E[i].y,&E[i].c);

    sort(E+1,E+1+M,cond);

    for(int i=1;i<=M;i++)
    {
        if(Find(E[i].x)!=Find(E[i].y))
            Unite(E[i].x,E[i].y),Stack[++Size]={E[i].x,E[i].y},cost+=E[i].c;
    }
    fprintf(OUT,"%d\n%d\n",cost,N-1);
    for(int i=1;i<N;i++)
        fprintf(OUT,"%d %d\n",Stack[i].first,Stack[i].second);
    return 0;
}