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

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;

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;
        f[i].push_back(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];
            for(itr=f[m].begin();itr!=f[m].end();itr++)
            {
                a[*itr]=a[mch.x];
                f[a[mch.x]].push_back((*itr));
            }
            while(f[m].size()>0)
                f[m].erase(f[m].begin());
        }
    }
    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;
}