#include <fstream>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 200200
ifstream f("apm.in");
int S=1,I=0;
const int D=9999;
char p[D+1];
inline void R(int&x)
{
    x=0;S=1;
    while(p[I]<40)
        if(++I>D)
        {
            I=0;
            f.read(p,D+1);
        }
    if(p[I]=='-')
        {
            S=-1;
            if(++I>D)
            {
                I=0;
                f.read(p,D+1);
            }
        }
    while(p[I]>47 && p[I]<58)
    {
        x=x*10+p[I]-48;
        if(++I>D)
        {
            I=0;
            f.read(p,D+1);
        }
    }
    x*=S;
}
int x,y,z,n,m,i[2*N],j,l,g[N],A,o=-1,h[N],s[2*N];
struct edge
{
    int x,y,c;
}v[2*N];
inline bool C(int a,int u)
{
    return(v[a].c<v[u].c);
}
int main()
{
    R(n);R(m);
    for(j=0;j<m;++j)
    {
        i[j]=j;
        R(v[j].x);R(v[j].y);R(v[j].c);
    }
    f.close();
    sort(i,i+m,C);++n;
    for(j=1;j<n;++j){h[j]=1;g[j]=j;}
    --n;
    for(j=0;h[1]<n;++j)
    {
        x=v[i[j]].x;y=v[i[j]].y;
        while(x>g[x])z=g[g[x]],g[x]=z,x=z;
        while(y>g[y])z=g[g[y]],g[y]=z,y=z;
        if(x!=y)
        {
            s[++o]=i[j];
            A+=v[i[j]].c;
            if(x>y)h[y]+=h[x],h[x]=0,g[x]=y;
            else h[x]+=h[y],h[y]=0,g[y]=x;
        }
    }
    ofstream G("apm.out");
    G<<A<<'\n'<<++o<<'\n';
    for(j=0;j<o;++j)
        G<<v[s[j]].x<<" "<<v[s[j]].y<<'\n';
    return 0;
}