#include <bits/stdc++.h>

using namespace std;

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

const int oo = (1 << 30),
          NMAX = 200000;

typedef pair<int, int> intPair;

class comp {
    public: bool operator()(const intPair& x, const intPair& y) const {
        return x.second > y.second;
    };
};

priority_queue<intPair, vector<intPair>, comp> Q;
vector<intPair> G[NMAX+1];
bool v[NMAX+1];
int T[NMAX+1], D[NMAX+1],
    N, M, cost;

void citire() {
    in >> N >> M;

    int x, y, c;

    for(int i = 1; i <= M; i++) {
        in >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
}

void prim() {
    int nA = N;
    while(nA) {
        int x = 0;
        while(v[x]) {
            x = Q.top().first;
            Q.pop();
        }
        v[x] = 1;
        cost += D[x];
        nA--;

        for(const auto& i: G[x])
            if(i.second < D[i.first] && !v[i.first]) {
                T[i.first] = x;
                D[i.first] = i.second;
                Q.push({i.first, i.second});
            }
    }
}

int main()
{
    citire();

    for(int i = 2; i <= N; i++)
        D[i] = oo;

    Q.push({1, 0});
    v[0] = 1;
    prim();

    out << cost << '\n' << N-1 << '\n';
    for(int i = 2; i <= N; i++)
        out << i << ' ' << T[i] << '\n';
    return 0;
}