#include <bits/stdc++.h>
#define ll long long
const int INF = 1000000000;
using namespace std;

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

void prim(const vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> ans;
    vector<int> dist(n, 69696969);
    vector<bool> vis(n);
    vector<int> parent(n);
    dist[0] = 0;
    pq.push({0, 0});
    while(!pq.empty()) {
        int v=pq.top().second;
        pq.pop();
        if(!vis[v] && v != 0) {
            ans.push_back({parent[v], v});
        }
        vis[v] = 1;
        for(auto u : adj[v]) {
            if(!vis[u.second] && dist[u.second]>u.first) {
                dist[u.second]=u.first;
                parent[u.second]=v;
                pq.push({u.first, u.second});
            }
        }
    }
    int cost = 0;
    for (auto v : dist) {
        cost += v;
    }
    fout << cost << endl;
    fout << n - 1 << endl;
    for (auto v : ans) {
        fout << v.first + 1 << " " << v.second + 1 << endl;
    }
}


void solve() {
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        x--;
        y--;
        adj[x].push_back({c, y});
        adj[y].push_back({c, x});
    }
    prim(adj);
}

int main() {
    int t = 1;
    // fin >> t;
    while (t--) {
        solve();
    }
    return 0;
}