#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 2e5 + 5;
const int INF = 1e9;

int n, m;
vector<pair<int, pair<int, int>>> G[NMAX];
pair<pair<int, int>, int> much[NMAX * 2];
int dist[NMAX], prevEdge[NMAX];
bool inTheMST[NMAX];

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, cost; fin >> u >> v >> cost;
        G[u].push_back({i, {v, cost}});
        G[v].push_back({i, {u, cost}});
        much[i] = {{u, v}, cost};
    }
}

int main() {
    read();

    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    vector<int> chosenEdges;
    set<pair<int, int>> Q;  // (dist, nod)
    Q.insert({0, 1});
    while (!Q.empty()) {
        auto scos = *Q.begin();
        Q.erase(Q.begin());
        int vertex = scos.second;

        if (vertex != 1)
            chosenEdges.push_back(prevEdge[vertex]);

        inTheMST[vertex] = true;

        for (auto v: G[vertex]) {
            int id = v.first;
            int neighbor = v.second.first, cost = v.second.second;
            if (!inTheMST[neighbor] && cost < dist[neighbor]) {
                auto it = Q.find({dist[neighbor], neighbor});
                if (it != Q.end())
                    Q.erase(it);
                dist[neighbor] = cost;
                prevEdge[neighbor] = id;
                Q.insert({dist[neighbor], neighbor});
            }
        }
    }

    int sum = 0;
    for (int mu: chosenEdges)
        sum += much[mu].second;

    fout << sum << "\n";
    fout << n - 1 << "\n";
    for (int mu: chosenEdges)
        fout << much[mu].first.first << " " << much[mu].first.second << "\n";

    return 0;
}