#include <fstream>
#include <algorithm>
#define NMAX 200000
#define MMAX 400000

using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int n, m, r1, r2, nrmuchii, cosmin;
int P[NMAX+5], H[NMAX+5];

struct muchie
{
    int x, y, c;
} G[MMAX+5], APM[NMAX+5];

void citire(void)
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
        fi>>G[i].x>>G[i].y>>G[i].c;
}

int cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

int findset(int nod)
{
    if(P[nod]!=nod)
        P[nod]=findset(P[nod]);
    return P[nod];
}

void mergeset(int a, int b)
{
    if(H[a]>H[b])
        P[b]=a;
    else
    {
        P[a]=b;
        if(H[a]==H[b])
            H[b]++;
    }
}

void afisare(void)
{
    fo<<cosmin<<"\n"<<n-1<<"\n";
    for(int i=1; i<=n-1; i++)
        fo<<APM[i].x<<" "<<APM[i].y<<"\n";
}

int main()
{
    citire();
    sort(G+1, G+m+1, cmp);
    for(int i=1; i<=n; i++)
        P[i]=i;
    for(int i=1; i<=m; i++)
    {
        r1=findset(G[i].x);
        r2=findset(G[i].y);
        if(r1!=r2)
        {
            mergeset(r1, r2);
            cosmin+=G[i].c;
            APM[++nrmuchii]=G[i];
        }
    }
    afisare();
    fi.close();
    fo.close();
    return 0;
}