#include <stdio.h>
#include<vector>
#include<map>
#include<queue>
using namespace std;
multimap <long,pair <long,long> > V;
long nr[200001],comp[200001];
long n,m,i,j,x,y,z,t;
queue <long> coada;
long CM(long x)
{
    long t=x,u;
    while (comp[t]!=t)
    {
        coada.push(t);
        t=comp[t];
    }
    while (coada.size()>0)
    {
        comp[coada.front()]=t;
        coada.pop();
    }
    return t;
}
void link (long &x, long &y)
{
    nr[comp[x]]+=nr[comp[y]];
    comp[CM(y)]=comp[CM(x)];
}
void kruskal()
{
    t=n-1;
    pair <long,long> u;
    queue < pair<long,long> > coada;
    long t1,t2,cost,sum;
    sum=0;
    while (t>0)
    {
        cost=(*V.begin()).first;
        u=(*V.begin()).second;
        V.erase(V.begin());
        t1=CM(u.first);
        t2=CM(u.second);
        if (t1!=t2)
        {
            sum+=cost;
            coada.push(u);
            if (nr[t1]>=nr[t2])
                link(u.first,u.second);
            else
                link(u.second,u.first);
            t--;
        }
    }
    printf ("%ld\n%ld\n",sum,n-1);
    while (coada.size()>0)
    {
        printf ("%ld %ld\n",coada.front().first,coada.front().second);
        coada.pop();
    }
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf ("%ld%ld",&n,&m);
    for (i=1;i<=n;i++)
        comp[i]=i,nr[i]=1;
    for (i=1;i<=m;i++)
    {
        scanf ("%ld%ld%ld",&x,&y,&z);
        V.insert(make_pair(z,make_pair(x,y)));
    }
    kruskal();
    return 0;
}