#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define  MaxN 200005
#define INF 2140000000
#define MAX 131072
using namespace std;
 
char f[MAX];
int pos=0,sign;
FILE *IN,*OUT;
void Read(int &nr)
{
    nr=0,sign=1;
    while(f[pos]>'9'||f[pos]<'0')
    {
        if(f[pos]=='-')
            sign=-1;
        pos++;
        if(pos==MAX)
            pos=0,fread(f,1,MAX,IN);
    }
    while(f[pos]<='9'&&f[pos]>='0')
    {
        nr=nr*10+f[pos++]-'0';
        if(pos==MAX)
            pos=0,fread(f,1,MAX,IN);
    }
    nr*=sign;
}
 
int v[MaxN],N,M,X,Y,cost;
struct Edge
{
    int x,y,cost;
}E[2*MaxN],O[MaxN];
void Unite(int x,int y)
{
    if(x!=y)v[y]=x;
}
int Find(int x)
{
    int y=x,aux;
    while(y!=v[y])
        y=v[y];
    while(x!=v[y])
    {
        aux=v[x];
        v[x]=v[y];
        x=aux;
    }
    return y;
}
bool cond(Edge a,Edge b)
{
    return a.cost<b.cost;
}
int main()
{
    IN=fopen("apm.in","r");
    OUT=fopen("apm.out","w");
    fread(f,1,MAX,IN);
     
    Read(N),Read(M);
    for(int i=1;i<=N;i++)
        v[i]=i;
    for(int i=1;i<=M;i++)
        Read(E[i].x),Read(E[i].y),Read(E[i].cost);
    sort(E+1,E+1+M,cond);
    int comp=0;
    int P=1;
    while(comp<N-1)
    {
        X=Find(E[P].x);
        Y=Find(E[P].y);
        if(X!=Y)
        {
            Unite(X,Y);
            cost+=E[P].cost;
            O[++comp]=E[P];
        }
        P++;
    }
    fprintf(OUT,"%d\n%d\n",cost,N-1);
    for(int i=1;i<N;i++)
        fprintf(OUT,"%d %d\n",O[i].x,O[i].y);
    return 0;
}