#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

const int MAXN = 200000;

int n, m;
vector<pair<int,int>> adj[MAXN + 5];

long long Prim(int start, vector<pair<int,int>> &mst) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    vector<int> d(n+1, 1e9), tata(n+1, 0);
    vector<bool> viz(n+1, false);

    d[start]=0;
    q.push({0, start});
    long long cost_total=0;

    while(!q.empty()) {
        pair<int,int> p = q.top();
        q.pop();

        int u = p.second;
        if(viz[u]==true) continue;
        viz[u] = true;
        cost_total += d[u];

        for(auto &edge : adj[u]) {
            int v=edge.first;
            int c=edge.second;
            if(c < d[v] && viz[v]==false) {
                d[v] = c;
                tata[v] = u;
                q.push({d[v], v});
            }
        }
    }

    for(int i=1;i<=n;i++) {
        if(tata[i]!=0) {
            mst.push_back({i, tata[i]});
        }
    }

    return cost_total;
}

int main() {
    f>>n>>m;
    for(int i=1;i<=m;i++) {
        int x, y, c;
        f>>x>>y>>c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }

    vector<pair<int,int>> mst;
    long long cost = Prim(1, mst);

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