#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define f first
#define s second
#define sf second.first
#define ss second.second

using namespace std;

int t[200005], nr[200005], nrv;
pair <int, int> v[200005];
priority_queue <pair <int, pair <int, int> > > q;
pair <int, pair <int, int> > p;

int ft (int x)
{
    return (x == t[x]) ? x : (t[x] = ft(t[x]));
}

int main()
{
    //ifstream in ("date.in");/*
    ifstream in ("apm.in");
    ofstream out ("apm.out");//*/

    int n, m, x, y, c, i, nrt = 0;
    in >> n >> m;
    for (i = 1; i <= n; ++i){
        t[i] = i;
        nr[i] = 1;
    }
    for (i = 0; i < m; ++i){
        in >> x >> y >> c;
        q.push({-c, {x, y}});
    }

    m = n - 1;
    while (m) {
        p = q.top();
        q.pop();
        x = ft (p.sf);
        y = ft (p.ss);
        if (x == y) {continue;}
        nrt -= p.f;
        --m;
        v[++nrv] = p.s;
        if (nr[x] > nr[y]) {
            nr[x] += nr[y];
            t[y] = x;
        }
        else {
            nr[y] += nr[x];
            t[x] = y;
        }
    }

    out << nrt << "\n" << n-1 << "\n";
    for (i = 1; i <= nrv; ++i){
        out << v[i].f << " " << v[i].s << "\n";
    }

    return 0;
}