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

#define maxN 200200

using namespace std;

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

struct edge {int x,y,c;} v[maxN];
int n,m,gr[maxN],nr,ans;
stringstream out;

void readData()
{
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
        fin>>v[i].x>>v[i].y>>v[i].c;
}

int getGroup(int x)
{
    if (gr[x]==x) return x;
    gr[x]=getGroup(gr[x]);
    return gr[x];
}

void makeGroup(int x, int y)
{
    gr[getGroup(x)]=getGroup(y);
}

bool cmp(edge x, edge y)
{
    return x.c < y.c;
}

int main()
{
    readData();
    sort(v+1, v+m+1, cmp);
    for (int i=1; i<=n; ++i)
        gr[i]=i;
    for (int i=1; i<=m; ++i)
        if (getGroup(v[i].x) != getGroup(v[i].y))
        {
            ++nr;
            ans+=v[i].c;
            makeGroup(v[i].x,v[i].y);
            out<<v[i].x<<' '<<v[i].y<<'\n';
        }
    fout<<ans<<'\n'<<nr<<'\n'<<out.str();
    return 0;
}