#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

const int NMAX = 200005;
const int MMAX = 500005;
int n, m;

struct Data {
    int node, cost, from;
    bool operator< (Data other) const {
        return cost > other.cost;
    }
};
vector<Data> g[NMAX];
vector<pair<int, int>> arb;
priority_queue<Data> hp;
bool visited[NMAX];

int main()
{
    ios::sync_with_stdio(false);
    in >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int x, y, c;
        in >> x >> y >> c;
        g[x].push_back({y, c, 0});
        g[y].push_back({x, c, 0});
    }
    hp.push({1, 0, 1});
    int s = 0, nmuc = -1;
    while(hp.size() > 0) {
        Data u = hp.top();
        hp.pop();
        if(!visited[u.node]) {
            nmuc ++;
            s += u.cost;
            arb.push_back({u.from, u.node});
            visited[u.node] = 1;
            for(Data i : g[u.node])
                if(!visited[i.node])
                    hp.push({i.node, i.cost, u.node});
        }
    }
    out << s << "\n" << nmuc << "\n";
    for(int i = 1;i < arb.size(); i ++)
        out << arb[i].first << " " << arb[i].second << "\n";
    return 0;
}