#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,m,viz[200005],a,b,aa[200005],bb[200005],rez,r1,r2;
long long rezz;
struct nod
{
    int x;
    int y;
    int cost;
}v[200005];
 
int cmp(const nod a,const nod b)
{
    return a.cost<b.cost;
}
 
int find(int t)
{
    while(viz[t]!=0) t=viz[t];
    return t;
}
 
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=m;i++) if (find(v[i].x)!=find(v[i].y))
            {
                rezz=rezz+v[i].cost;
                viz[find(v[i].y)]=find(v[i].x);
                rez++;
                aa[rez]=v[i].x;
                bb[rez]=v[i].y;
    }
    printf("%lld\n",rezz);
    printf("%d\n",rez);
    for (i=1;i<=rez;i++)printf("%d %d\n",bb[i],aa[i]);
    return 0;
}