#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct graf
{
    int x, y, c;
}v[200001];
int poz[400001], t[400001], nrcomp, s, n, m;
bool cmp(graf i, graf j)
{
    return i.c < j.c;
}
int GetRoot(int x)
{
    return t[x]==x?x:(t[x]=GetRoot(t[x]));
}
void Unite(int x, int y)
{
    t[GetRoot(x)] = GetRoot(y);
}
void Kruskal()
{
    for ( int i = 1; i <= m; i++ )
        if ( GetRoot(v[i].x) != GetRoot(v[i].y) )
        {
            poz[++nrcomp] = i;
            s += v[i].c;
            Unite(v[i].x, v[i].y);
        }
}
int main()
{
    fin >> n >> m;
    for( int i = 1; i <= m; i++ )
        fin >> v[i].x >> v[i].y >> v[i].c;
    sort(v+1,v+m+1,cmp);
    for ( int i = 1; i <= n; i++ )
        t[i] = i;
    Kruskal();
    fout << s << '\n' << nrcomp << '\n';
    for (int i = 1; i <= nrcomp; i++ )
        fout << v[poz[i]].x << ' ' << v[poz[i]].y << '\n';
    fin.close();
    fout.close();
    return 0;
}