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

using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int n, m, cosmin, nrMuchii;
int P[NMAX+5];
struct MUCHIE
{
    int x, y, c;
} G[NMAX+5], APM[NMAX+5];

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

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

bool multDif(int x, int y)
{
    int r1, r2;
    r1=dfs(x);
    r2=dfs(y);
    if(r1!=r2)
        return 1;
    return 0;
}

int radacina(int nod)
{
    while(P[nod]!=nod)
        nod=P[nod];
    return nod;
}

void reuniune(int x, int y)
{
    int r1, r2;
    r1=radacina(x);
    r2=radacina(y);
    P[r1]=r2;
}

int main()
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
        fi>>G[i].x>>G[i].y>>G[i].c;
    sort(G+1, G+m+1, cmp);

    for(int i=1; i<=n; i++)
        P[i]=i;
    for(int i=1; i<=m; i++)
        if(multDif(G[i].x, G[i].y))
        {
            APM[++nrMuchii]=G[i];
            cosmin+=G[i].c;
            reuniune(G[i].x, G[i].y);
        }

    fo<<cosmin<<"\n"<<n-1<<"\n";
    for(int i=1; i<=n-1; i++)
        fo<<APM[i].x<<" "<<APM[i].y<<"\n";
    fi.close();
    fo.close();
    return 0;
}