#include <fstream>
#include <vector>
#include <algorithm>
#define NX 200001
#define MX 400001
using namespace std;

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

struct muchie
{
    int i,j,c;
};

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

int n,m;
vector<muchie> v, drum;
int t[NX],suma;

void citire()
{
    int i;
    muchie e;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>e.i>>e.j>>e.c;
        v.push_back(e);
    }

    sort(v.begin(), v.end(), cmp);
}

int Find(int x)
{
    int r=x,y;

    while(t[r])
    {
        r = t[r];
    }

    while(t[x])
    {
        y = t[x];
        t[x] = r;
        x = y;
    }

    return r;
}

//Union este prea scurt, se poate scrie direct

int main()
{
    muchie u;
    int radi,radj;
    vector<muchie>::iterator it;

    citire();
    for(it=v.begin(); it!=v.end(); it++)
    {
        u = *it;
        radi = Find(u.i);
        radj = Find(u.j);
        if(radi != radj)    //Union
        {
            t[radi] = radj;
            suma += u.c;
            drum.push_back(u);
        }
    }

    fout<<suma<<'\n';
    fout<<drum.size()<<'\n';
    for(it=drum.begin(); it!=drum.end(); it++)
    {
        fout<<it->i<<' '<<it->j<<'\n';
    }

    v.clear();
    drum.clear();

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