#include <bits/stdc++.h>
using namespace std;

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

struct Edge {
    int w = INT_MAX, to = -1;
    bool operator<(Edge const& other) const {
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};

int main() {
    int n, m, i, x, y, c, cost = 0;
    f >> n >> m;
    vector<vector<Edge>> edges(n + 1);
    vector<Edge> minE(n + 1);
    vector<pair<int, int>> res;
    vector<bool> selected(n + 1, false);

    minE[1].w = 0;

    for(i = 0; i < m; ++i) {
        f >> x >> y >> c;
        Edge e = Edge();
        e.to = y;
        e.w = c;
        edges[x].push_back(e);
        e.to = x;
        e.w = c;
        edges[y].push_back(e);
    }

    set<Edge> s;
    s.insert({0, 1});
    for(i = 0; i < n; ++i) {
        if(s.empty()) {
            g << "Nu exista apm!";
            exit(0);
        }

        int node = s.begin()->to;
        selected[node] = true;
        cost = cost + s.begin()->w;
        s.erase(s.begin());

        if(minE[node].to != -1)
            res.push_back({node, minE[node].to});
            //cout << node << ' ' << minE[node].to << '\n';

        for(auto& e: edges[node]) {
            if(!selected[e.to] && e.w < minE[e.to].w) {
                s.erase({minE[e.to].w, e.to});
                minE[e.to] = {e.w, node};
                s.insert({e.w, e.to});
            }
        }

    }

    g << cost << '\n' << res.size() << '\n';
    for(auto& e: res) {
        g << e.first << ' ' << e.second << '\n';
    }
    return 0;
}