#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int cost, h[200005],tata[200005],N,M,x,y,c,costf,muchii;
struct mchh
{
    int a,b,cost;
}mch[200005];
struct solutie
{
    int a,b;
}sol[200005];
int TATA(int x)
{
    while(x!=tata[x])return TATA(tata[x]);
    return x;
}
int muchie(int r1,int r2)
{
    r1=TATA(r1);
    r2=TATA(r2);
    if(r1==r2)return 0;
    if(h[r1]<h[r2])tata[r1]=r2;
    else if(h[r1]>h[r2])tata[r2]=r1;
    else
    {
        tata[r2]=r1;
        h[r1]++;
    }
    return 1;
}
bool compare(mchh x,mchh y)
{
    return (x.cost<y.cost);
}
void KRUSKAL()
{
    int k=1,r1,r2;
    while(muchii<N-1)
    {
        r1=mch[k].a;
        r2=mch[k].b;
        if(muchie(r1,r2))
        {
            costf+=mch[k].cost;
            sol[++muchii].a=r1;
            sol[muchii].b=r2;
           // muchii++;
        }
        k++;

    }
}
int k;
int main()
{
    f>>N>>M;
    for(int i=1; i<=M; i++)
    {
        f>>x>>y>>c;
        mch[i].a=x;
        mch[i].b=y;
        mch[i].cost=c;
    }
    sort(mch+1,mch+M+1,compare);
    //for(int i=1; i<=M; i++)g<<mch[i].a<<" "<<mch[i].b<<" "<<mch[i].cost<<'\n';
    for(int i=1; i<=N; i++)tata[i]=i,h[i]=1;
    KRUSKAL();
    g<<costf<<'\n';
    g<<muchii<<'\n';
    for(int i=1;i<=muchii;i++)
    {
        g<<sol[i].a<<" "<<sol[i].b<<'\n';
    }
    return 0;
}