#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

const int MAX_N = 200000;

using namespace std;

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

class Node {
public:
    int v, c, p;

    Node(int a = 0, int b = 0, int d = 0) {
        v = a;
        c = b;
        p = d;
    }

    bool operator < (const Node other) const {
        return this->c > other.c;
    }
};

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

void apm() {
    priority_queue<Node> pq;
    pq.push(Node(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.c;
        ans.push_back({u.p, u.v});

        for(auto v : G[u.v])
            if(!visited[v.v])
            pq.push(Node(v.v, v.c, u.v));
    }
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back(Node(b, c, a));
        G[b].push_back(Node(a, c, b));
    }

    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;
}