#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,cost,h[200100],tata[200100];

struct Muchie
{
    int a,b,c;
}mh[400100];

struct sol
{
    int start,finish;
}sol[200100];

int compare(Muchie A, Muchie B)
{
    return (A.c<B.c);
}

int TATA(int k)
{
    while(k!=tata[k])return TATA(tata[k]);
    return k;
}

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[r2]<h[r1])tata[r2]=r1;
    else {tata[r1]=r2;h[r2]++;}

    return 1;
}

void kruskal()
{
    int k=1,muchii=1,r1,r2;
    while(muchii<=n-1)
    {
        r1=mh[k].a;
        r2=mh[k].b;
        //cout<<muchie(r1,r2)<<'\n';
        if(muchie(r1,r2))
        {
           cost+=mh[k].c;
           sol[muchii].start=r1;
           sol[muchii].finish=r2;
           muchii++;
        }
        k++;
    }
}

int i;
int main()
{
    f>>n>>m;

    for(i=1;i<=n;i++)
    {
        tata[i]=i;
        h[i]=1;
    }

    for(i=1;i<=m;i++)
    {
        f>>mh[i].a>>mh[i].b>>mh[i].c;
    }
    sort(mh+1,mh+m+1,compare);

    kruskal();
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        g<<sol[i].start<<" "<<sol[i].finish<<'\n';
    }
    return 0;
}