#include <iostream>
#include <fstream>
#include <queue>
#define INF 0xffffff

using namespace std;

vector <vector <pair <int, int> > > mat;
priority_queue <pair <int, pair <int, int> > > q;/// x->y with c: <c, <x, y> >
vector <int> v;
queue <pair <int, int> > af;

int main()
{
    ifstream in ("apm.in");
    ofstream out ("apm.out");
    int n, m, x, y, c, i, nr = 0;
    in >> n >> m;
    mat.resize (n+1);
    v.resize (n+1, 0);v[1] = 1;

    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].push_back (make_pair(y, -c));
        mat[y].push_back (make_pair(x, -c));
    }
    vector <pair <int, int> > ::iterator k;
    for (k = mat[1].begin(); k != mat[1].end(); ++k) {q.push (make_pair (k->second, make_pair(1, k->first)));}

    pair <int, pair <int, int> > now;
    while (!q.empty()) {
        now = q.top();
        q.pop();
        c = -now.first;
        x = now.second.first;
        y = now.second.second;

        if (v[x] + v[y] != 1) {continue;}

        //cout << x << " " << y << " " << c << "\n";
        nr += c;
        af.push (now.second);
        if (v[x] == 0) {y = x;}
        v[y] = 1;
        for (k = mat[y].begin(); k != mat[y].end(); ++k) {
            if (v[y] + v[k->first] == 1) {
                q.push (make_pair (k->second, make_pair(y, k->first)));
            }
        }

    }

    out << nr << "\n" << n - 1 << "\n";
    pair <int, int> a;
    while (!af.empty()) {
        a = af.front();
        af.pop();
        out << a.first << " " << a.second << "\n";
    }

    return 0;
}