#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC

using namespace std;
struct edge
{
    int x,y,c;
    bool operator <(const edge &other) const
    {
        return c<other.c;
    }
};

edge v[400001];

int conex[200001],f[400001];

int compute_rad(int x)
{
    int r;
    if(conex[x]==0)
        return x;
    conex[x]=r=compute_rad(conex[x]);
    return r;
}

int main()
{
    int n,m,i,ct;
    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].c);
    sort(v+1,v+1+m);
    ct=1;
    i=1;
    long long rez=0;
    while(i<=m && ct<n)
    {
        int rx=compute_rad(v[i].x);
        int ry=compute_rad(v[i].y);
        if(rx!=ry)
        {
            conex[rx]=ry;
            rez+=v[i].c;
            f[i]=1;
            ct++;
        }
        i++;
    }
    printf("%lld\n%d\n",rez,n-1);
    for(i=1; i<=m; i++)
        if(f[i])
            printf("%d %d\n",v[i].x,v[i].y);

    return 0;
}