#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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

const int maxn = 2e5 + 5;
const int oo = 1 << 30;
vector < pair <int,int> > G[maxn];
pair <int,int> Apm[maxn];
bitset <maxn> Vis;
int Dist[maxn], lg, n;

class Node {
public:
    int dad, node, cost;
    inline bool operator () (const Node& A, const Node& B) {
        return A.cost > B.cost;
    }
};

Node Group (int x, int y, int z) {
    Node A;
    A.dad = x, A.node = y, A.cost = z;
    return A;
}

int Prim (int start) {
    vector < pair <int,int> > :: iterator it;
    priority_queue <Node, vector <Node>, Node> H;
    int node, cost, dad, i, min_cost = 0;
    for (i = 1; i <= n; i++) {
        Dist[i] = oo;
    }
    Dist[start] = 0;
    H.push(Group(0, start, 0));
    while (!H.empty()) {
        dad = H.top().dad;
        node = H.top().node;
        cost = H.top().cost;
        H.pop();
        if (node != start && Vis[node] == false) {
            min_cost += cost;
            Apm[++lg] = make_pair(dad, node);
        }
        Vis[node] = true;
        for (it = G[node].begin(); it != G[node].end(); it++) {
            if (Dist[it->first] > it->second && Vis[it->first] == false) {
                Dist[it->first] = it->second;
                H.push(Group(node, it->first, it->second));
            }
        }
    }
    return min_cost;
}

int main() {
    ios_base :: sync_with_stdio (false);
    int m, x, y, c, i;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
        G[y].push_back(make_pair(x, c));
    }
    fout << Prim(1) << "\n" << n - 1 << "\n";
    for (i = 1; i < n; i++) {
        fout << Apm[i].first << " " << Apm[i].second << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}