#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <climits>

using namespace std;

#define maxN 200005
#define INF INT_MAX

struct cmp {
    bool operator() (const pair<int, int> &lhs, const pair<int, int> &rhs) const {
        return (lhs.second > rhs.second);
    }
};

int cost[maxN], parent[maxN], N, M;
bool viz[maxN];
vector <pair <int, int> > G[maxN], edgeSol;
priority_queue<pair <int, int>, vector <pair <int, int> >, cmp> Q;

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

    int costSol = 0;

    f >> N >> M;
    for (int i = 0; i < M; ++i) {
        int x, y, c;

        f >> x >> y >> c;

        G[x].push_back(make_pair(y, c));
        G[y].push_back(make_pair(x, c));
    }

    for (int i = 1; i <= N; ++i) {
        cost[i] = INF;
    }

    cost[1] = 0;
    parent[1] = 1;

    Q.push(make_pair(1, 0));
    viz[0] = true;

    for (int T = 1; T <= N; ++T) { //add N vertices to the apm
        int root = 0;
        int rootCost;

        while (viz[root]) {
            root = Q.top().first;
            rootCost = Q.top().second;
            Q.pop();
        }

        viz[root] = true;
        costSol += rootCost;
        edgeSol.push_back(make_pair(parent[root], root));

        for (unsigned int i = 0; i < G[root].size(); ++i) {
            int neighbor = G[root][i].first;
            int edgeCost = G[root][i].second;

            if (viz[neighbor] || edgeCost >= cost[neighbor]) {
                continue;
            }

            cost[neighbor] = edgeCost;
            parent[neighbor] = root;
            Q.push(make_pair(neighbor, cost[neighbor]));
        }
    }

    g << costSol << "\n" << edgeSol.size() - 1 << "\n";
    for (unsigned int i = 1; i < edgeSol.size(); ++i) {
        g << edgeSol[i].first << " " << edgeSol[i].second << "\n";
    }

    return 0;
}