#include <bits/stdc++.h>

using namespace std;

struct str
{
    int x,y,c;
};

str v[400010];
int rad[200010],rez[200010];

int cmp(str a,str b)
{
    return a.c<b.c;
}

int radacina(int x)
{
    int y=x;
    while(x!=rad[x]) x=rad[x];
    while(rad[y]!=x)
    {
        int aux=rad[y];
        rad[y]=x;
        y=aux;
    }
    return x;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,l=0,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    for(int i=1;i<=n;i++) rad[i]=i;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int x=radacina(v[i].x),y=radacina(v[i].y);
        if(x==y) continue;
        rad[x]=y;
        ans+=v[i].c;
        rez[++l]=i;
        if(l==n-1) break;
    }
    printf("%d\n%d\n",ans,l);
    for(int i=1;i<=l;i++) printf("%d %d\n",v[rez[i]].x,v[rez[i]].y);
    return 0;
}