#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

#define lim 200100
struct nod{int x,y,c;} ini[2*lim];
int d[lim],n,m,rez;

bool cmp(nod a, nod b)
{
    return a.c<b.c;
}

int get_dad(int x)
{
    if(d[x]!=x)   d[x]=get_dad(d[x]);
    return d[x];
}

int sol[lim],dr;

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        d[i] = i;

    for(int i=1; i<=m; i++)
        fin>>ini[i].x>>ini[i].y>>ini[i].c;

    sort(ini+1, ini+m+1, cmp);

    for(int i=1; i<=m; i++)
    {
        if(get_dad(ini[i].x) != get_dad(ini[i].y))
        {
            d[get_dad(ini[i].x)]=get_dad(ini[i].y);
            rez+=ini[i].c;
            sol[++dr]=i;
        }
    }

    fout<<rez<<'\n'<<dr<<'\n';
    for(int i=1; i<=dr; i++)
        fout<<ini[sol[i]].x<<' '<<ini[sol[i]].y<<'\n';

    fin.close();
    fout.close();
    return 0;
}