#include <bits/stdc++.h>
#define inf 2e8

using namespace std;

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

vector < vector < pair <int, int> > > adj;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater <pair<int, int> > > pq;
vector <int> viz;
vector <int> tata;
int n, m, k, s;


int main() {
    fin >> n >> m;
    adj.resize(n + 1);
    viz.resize(n + 1);
    tata.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        adj[x].push_back({c, y});
        adj[y].push_back({c, x});
    }
    int costTotal = 0;
    tata[1] = 0;
    vector < pair <int, int> > rez;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto aux = pq.top();
        pq.pop();
        int nod = aux.second;
        int cost = aux.first;
        if (!viz[nod]) {
            viz[nod] = 1;
            costTotal += cost;
            if (nod != 1)
                rez.push_back({tata[nod], nod});
        }
        else continue;

        for (auto x: adj[nod]) {
            if (!viz[x.second]) {
                tata[x.second] = nod;
                pq.push(x);
            }
        }
    }
    fout << costTotal << "\n";
    fout << rez.size() << "\n";
    for (auto x: rez) {
        fout << x.first << " " << x.second << "\n";
    }

return 0;
}