#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct mu{
    int a,b,c;
}v[400003];
int tata[200001];
vector <int>w;

int rad(int nod)
{
    if(tata[nod]==nod)return nod;
    else tata[nod]=rad(tata[nod]);
    return tata[nod];
}
void uni(int a, int b)
{
    tata[b]=a;
}


bool comp(mu a, mu b)
{
    return a.c<b.c;
}

int main()
{freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
int i,j,n,m,a,b,c,cost=0,N=0,nr=0;
bool ok=true;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
    scanf("%d%d%d",&a,&b,&c);
   v[i].a=a;
   v[i].b=b;
   v[i].c=c;
}
for(i=1;i<=n;i++)tata[i]=i;


sort(v+1,v+m+1,comp);

for(i=1;i<=m&&nr<n;i++)
{
    a=rad(v[i].a);
    b=rad(v[i].b);
    if(a!=b)
    {nr++;
        uni(a,b);
        cost+=v[i].c;
        w.push_back(v[i].a);
        w.push_back(v[i].b);N=N+2;

    }
}
printf("%d\n%d\n",cost,N/2);
for(i=0;i<N;i=i+2)printf("%d %d\n",w[i],w[i+1]);


    return 0;
}