#include <bits/stdc++.h>
#define MM 400001
#define NM 200001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int x, y, c, OK;
}v[MM];

int t[NM];
int n, m, ct, nr;

int comp(muchie u,muchie v)
{
    return u.c<v.c;
}

int radacina(int x)
{
    int y,aux,r;

    ///aflam radacina
    r=x;
    while(t[r]!=0)
        r=t[r];

    ///facem compresia drumurilor
    y=x;
    while(t[y]!=0)
    {
        aux=t[y];
        t[y]=r;
        y=t[y];
    }
    return r;

}
int main()
{
    int i,rx,ry,x,y;
    ///citire
    fin >> n >> m;
    for(i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].c;

    /// pas1
    for(i=1; i <= n; i++)
        t[i] = 0;

    /// pas2 - sortare
   sort(v+1,v+m+1,comp);

    //! pas3
    ct = 0; nr = 0; i = 1;
    while(nr < n-1)
    {
        x = v[i].x; y = v[i].y;
        rx=radacina(x);
        ry=radacina(y);

        if(rx != ry)
        {
            ct=ct+v[i].c;
            t[ry]=rx;
            v[i].OK = 1;
            nr++;
        }
        i++;
    }

    /// pass4 - afisare

    fout << ct << '\n'<<n-1<<'\n';
    for(i = 1; i <= m; i++)
        if(v[i].OK == 1)
            fout << v[i].x << ' ' << v[i].y << '\n';
}