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

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

struct muc
{
    int a,b,c;
};
int n,m;
muc v[MX];
int t[NX];
int total;
vector< pair<int, int> > sol;
vector<int> r[NX];

bool comp(muc a, muc b)
{
    return a.c < b.c;
}

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }

    for(i=1; i<=n; i++)
    {
        t[i] = i;
        r[i].push_back(i);
    }
}

void Union(int x, int y)
{
    vector<int>::iterator it;
    for(it=r[y].begin(); it!=r[y].end(); it++)
    {
        r[x].push_back(*it);
        t[*it] = x;
    }

    r[y].clear();
}

void kruskal()
{
    int i,a,b,c,x,y;
    pair<int, int> e;
    for(i=1; i<=m; i++)
    {
        a = v[i].a;
        b = v[i].b;
        c = v[i].c;

        x = t[a];
        y = t[b];
        if(x != y)
        {
            if(r[x].size() > r[y].size()) Union(x, y);
            else Union(y, x);
            total += c;
            e.first = a;
            e.second = b;
            sol.push_back(e);
        }
    }
}

int main()
{
    pair<int, int> e;

    citire();

    sort(v+1, v+m+1, comp);
    kruskal();

    fout<<total<<'\n';
    fout<<sol.size()<<'\n';
    while(!sol.empty())
    {
        e = sol.back();
        sol.pop_back();
        fout<<e.first<<' '<<e.second<<'\n';
    }

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