#include <fstream>
#include<algorithm>
using namespace std;
#define N 200200
#define s second
#define f first
#define mp make_pair
ifstream f("apm.in");
int S,I;
const int D=999999;
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,j,l,g[N],A,o=-1,h[N],s[2*N];
pair<int,pair<int,int> >v[2*N];
int main()
{
    R(n);R(m);
    for(j=0;j<m;++j)
        R(v[j].s.f),R(v[j].s.s),R(v[j].f);
    sort(v,v+m);++n;
    for(j=1;j<n;++j)h[j]=1,g[j]=j;
    --n;
    for(j=0;h[1]<n;++j)
    {
        x=v[j].s.f;y=v[j].s.s;
        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]=j;
            A+=v[j].f;
            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]].s.f<<" "<<v[s[j]].s.s<<'\n';
    return 0;
}