#include<cstdio>
#include<algorithm>
using namespace std;
int t[200005],h[200005];
struct DATA
{
    int x,y,c;
};
DATA v[400005],sol[400005];
int findset(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool unionset(int x,int y)
{
    int tx,ty;
    tx=findset(x);
    ty=findset(y);
    if(tx==ty)
        return 0;
    if(h[tx]==h[ty])
    {
        h[tx]++;
        t[ty]=tx;
    }
    else
        if(h[tx]<h[ty])
            t[tx]=ty;
        else
            t[ty]=tx;
    return 1;
}
bool cmp(DATA a,DATA b)
{
    return a.c<b.c;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; ++i)
    {
         int a,b,z;
         scanf("%d%d%d",&a,&b,&z);
         v[i].x=a;
         v[i].y=b;
         v[i].c=z;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1; i<=n; ++i)
    {
        t[i]=i;
        h[i]=1;
    }
    int total=0;
    int j=0;
    for(int i=1; i<=m && j<n-1; ++i)
    {
        if(unionset(v[i].x,v[i].y))
        {
            total+=v[i].c;
            sol[++j]=v[i];
        }
    }
    printf("%d\n%d\n",total,j);
    for(int i=1; i<=j; ++i)
        printf("%d %d\n",sol[i].x,sol[i].y);
    return 0;
}