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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAXN = 200010;

struct Edge {
    int from, to, cost;
    bool operator<(const Edge& other) const {
        return cost > other.cost;
    }
};

priority_queue<Edge> q;
vector<pair<int, int> > graph[MAXN], sol;
bool used[MAXN];
int n, m, nr, cost;

void read() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].pb({y, c});
        graph[y].pb({x, c});
    }
}

void solve() {
    used[1] = 1;
    for (const auto& it: graph[1])
        q.push({1, it.first, it.second});
    while (!q.empty()) {
        Edge e = q.top();
        int from = e.from, to = e.to;
        q.pop();
        if (used[from] == 1 && used[to] == 1)
            continue;
        cost += e.cost;
        sol.pb({from, to});
        if (used[from] == 0)
            to = from;
        used[to] = 1;
        ++nr;
        if (nr == n - 1)
            break;
        for (const auto &it: graph[to])
            if (used[it.first] == 0)
                q.push({to, it.first, it.second});
    }
}

void print() {
    fout << cost << '\n' << nr << '\n';
    for (const auto& it: sol)
        fout << it.first << ' ' << it.second << '\n';
}

int main() {
    read();
    solve();
    print();
    return 0;
}