#include <stdio.h>
#include<vector>
#include<map>
#include<queue>
using namespace std;

vector < vector< pair <long,long> > > graf,NOU;
vector< pair <long,long> > tmp;
multimap <long,pair <long,long> > V;
vector <long> nr,comp;
long n,m,i,j,x,y,z,t;
long CM(long x)
{
    queue <long> coada;
    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);
    tmp.push_back(make_pair(0,0));
    for (i=0;i<=n;i++)
        graf.push_back(tmp),NOU.push_back(tmp),comp.push_back(i),nr.push_back(1);
    for (i=1;i<=m;i++)
    {
        scanf ("%ld%ld%ld",&x,&y,&z);
        graf[x].push_back(make_pair(y,z));
        graf[y].push_back(make_pair(x,z));
        V.insert(make_pair(z,make_pair(x,y)));
    }
    kruskal();
    return 0;
}