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

using namespace std;

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

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

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

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;
        q[i].push(i);
    }

    for(it=v.begin();it!=v.end();it++)
    {
        mch=*it;
        if(a[mch.x]!=a[mch.y])
        {
            s+=mch.l;
            r.push_back(mch);
            m=a[mch.y];
            while(!q[m].empty())
            {
                q[a[mch.x]].push(q[m].front());
                a[q[m].front()]=a[mch.x];
                q[m].pop();
            }
        }
    }
    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;
}