#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct muchie
{
    int x, y, l;
}mch;

int n, m, i, s, tx, ty, a[200005];

vector <muchie> v;
vector <muchie>::iterator it;
vector <muchie> r;
queue <int> q[200005];

int T(int x)
{
    if(a[x]!=x) a[x]=T(a[x]);
    return a[x];
}

bool cmp(muchie a, muchie b)
{
    return a.l<b.l;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &mch.x, &mch.y, &mch.l);
        v.push_back(mch);
    }
    sort(v.begin(), v.end(), cmp);

    s=0;
    for(i=1;i<=n;i++)
        a[i]=i;

    for(it=v.begin();it!=v.end();it++)
    {
        mch=*it;
        tx=T(mch.x);
        ty=T(mch.y);
        if(tx!=ty)
        {
            a[tx]=ty;
            s+=mch.l;
            r.push_back(mch);
            m=a[mch.y];
        }
    }
    printf("%d\n", s);
    printf("%d\n", n-1);
    for(it=r.begin();it!=r.end();it++)
        printf("%d %d\n", (*it).x, (*it).y);
    return 0;
}