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

using namespace std;

long long n, m, x, y, c, parent[200005], comp[200005], cost;

struct nod
{
    long long x, y, c;
}p;

vector<nod> v;
vector<pair<long long, long long> > rez;

long long par(long long x)
{
    if(parent[x] == x) return x;
    else return parent[x] = par(parent[x]);
}

void un(nod p)
{
    long long x, y;
    x = par(p.x);
    y = par(p.y);
    if(x != y)
    {
        if(comp[y] >= comp[x]) swap(x, y);
        comp[x] += comp[y];
        cost += p.c;
        parent[y] = x;
        rez.push_back({p.x, p.y});
    }
}

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

ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
    f >> n >> m;
    for(long long i = 1; i <= n; i ++) parent[i] = i, comp[i] = 1;
    for(long long i = 1; i <= m; i ++)
    {
        f >> p.x >> p.y >> p.c;
        v.push_back(p);
    }
    sort(v.begin(), v.end(), cmp);

    for(long long i = 0; i < m; i ++)
    {
        ///cout << v[i].x << ' ' << v[i].y << ' ' << v[i].c << '\n';
        un(v[i]);
    }
    g << cost << '\n' << rez.size() << '\n';
    for(auto e : rez) g << e.first << ' ' << e.second << '\n';

}