#include <bits/stdc++.h>

const int MAX_N = 200000;

using namespace std;

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

struct Node {
    int v, cost, p;
    bool operator < (const Node &other) const {
        return this-> cost > other.cost;
    }
};

int n, m, s;
bitset<MAX_N + 5> visited;
vector<Node> vecini[MAX_N + 5];
vector<pair<int, int> > ans;

void apm() {
    priority_queue<Node> pq;
    pq.push({1, 0});

    while(!pq.empty()) {
        while(!pq.empty() && visited[pq.top().v] == 1)
            pq.pop();
        if(pq.empty())
            break;
        Node u = pq.top();
        pq.pop();

        visited[u.v] = 1;
        s += u.cost;
        ans.push_back({u.p, u.v});

        for(auto v : vecini[u.v])
            if(!visited[v.v])
                pq.push(v);
    }
}
int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        vecini[x].push_back({y, c, x});
        vecini[y].push_back({x, c, y});
    }

    apm();

    fout << s << '\n' << ans.size() - 1 << '\n';
    for(int i = 1; i < ans.size(); i++)
        fout << ans[i].first << ' ' << ans[i].second << '\n';
    return 0;
}