/**
  * Krizbai Matyas
  * 513
  * kmim2369
  **/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void beolvas(int &n, vector<vector<pair<int, int>>> &adj) {
    ifstream fin("apm.in");
    int m;
    fin >> n >> m;
    adj.resize(n+1);
    while(m--) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
        adj[v].push_back(make_pair(w, u));
    }
    fin.close();
}

void prim(int n, vector<vector<pair<int, int>>> &adj) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> ans;
    vector<int> dist(n+1, 69696969);
    vector<bool> vis(n+1);
    vector<int> parent(n+1);
    int source=1;
    dist[source]=0;
    pq.push({0, source});
    while(!pq.empty()) {
        int v=pq.top().second;
        pq.pop();
        if(!vis[v] && v!=source) {
            ans.push_back({parent[v], v});
        }
        vis[v]=true;
        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 sum=0;
    for(int i=1; i<=n; i++) {
        sum+=dist[i];
    }

    ofstream fout("apm.out");

    fout << sum << '\n' << ans.size() << '\n';
    for(auto it : ans) {
        fout << it.first << ' ' << it.second << '\n';
    }
}

int main() {
    int n;
    vector<vector<pair<int, int>>> adj;
    beolvas(n, adj);
    prim(n, adj);
    return 0;
}