#include <fstream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

#define Inf (1<<31)-1
#define NMax 200001

using namespace std;

vector<pair<int, int> > v[NMax], apme;
int C[NMax], P[NMax];
bool viz[NMax];
set<pair<int, pair<int, int> > > q;
int n, m, x, y, z, cost;

int main()
{
    ifstream fin ("apm.in");
    ofstream fout ("apm.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> x >> y >> z,
        v[x].push_back (make_pair (y, z)),
        v[y].push_back (make_pair (x, z));

    for (int i = 1; i <= n; i++)
        C[i] = Inf, P[i] = -1, viz[i] = 0;

    viz[1] = 1;
    for (int i = 0; i < v[1].size (); i++)
        C[v[1][i].first] = v[1][i].second,
        P[v[1][i].first] = 1,
        q.insert (make_pair ( C[v[1][i].first], make_pair (1, v[1][i].first)));

    for (int i = 1; i < n; i++) {
        int c = q.begin ()->first;
        pair<int, int> e = q.begin ()->second;
        q.erase (q.begin ());

        viz[e.second] = 1;
        apme.push_back (e);
        cost += c;

        for (vector<pair<int, int> >::iterator i = v[e.second].begin (); i != v[e.second].end (); i++)
            if (!viz[i->first] && i->second < C[i->first]) {
                set<pair<int, pair<int, int> > >::iterator it = q.find ( make_pair ( C[i->first], make_pair (P[i->first], i->first) ) );
                if (it != q.end ())
                    q.erase ( it );

                C[i->first] = i->second;
                P[i->first] = e.second;
                q.insert (make_pair ( C[i->first], make_pair (P[i->first], i->first)));
            }
    }

    fout << cost << '\n' << apme.size () << '\n';
    for (int i = 0; i < apme.size (); i++)
        fout << apme[i].first << ' ' << apme[i].second << '\n';
    return 0;
}