#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const char* inFile = "apm.in";
const char* outFile = "apm.out";

struct edge_type{
    unsigned x, y;
    short cost;
};

bool cond(edge_type A, edge_type B)
{
    return A.cost <= B.cost;
}

int main(void)
{
    unsigned N, M;
    freopen(inFile, "r", stdin);
    cin >> N >> M;
    vector<pair<unsigned, short> > v[N + 1];
    for(unsigned i = 0; i != M; ++i)
    {
        unsigned X, Y;
        short C;
        cin >> X >> Y >> C;
        v[X].pb(make_pair(Y, C));
        v[Y].pb(make_pair(X, C));
    }
    vector<bool> viz(N + 1, false);
    set<pair<unsigned, unsigned> > s;
    unsigned curr = 1, pos = 0;
    long long costMin = 0;
    vector<edge_type> q;
    for(unsigned sel = 1; sel != N; ++sel)
    {
        viz[curr] = true;
        for(auto k : v[curr])
            if(!viz[k.first])
                q.pb({k.first, curr, k.second});
        unsigned node = 0;
        edge_type edge;
        sort(q.begin() + pos, q.end(), &cond);
        while(!node)
        {
            edge = q[pos++];
            if(!viz[edge.x] || !viz[edge.y])
            {
                node = (!viz[edge.x] ? edge.x : edge.y);
                costMin += edge.cost;
            }
        }
        s.insert(make_pair(edge.x, edge.y));
        curr = node;
    }
    freopen(outFile, "w", stdout);
    cout << costMin << endl << N - 1;
    for(auto k : s)
        cout << endl << k.first << ' ' << k.second;
    fclose(stdin), fclose(stdout);
    return 0;
}