#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> G[200001];
bitset<200001> viz;
int v[200001], p[200001];
int n, m;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> H;

int main()
{
    vector<pair<int, int>> sol;
    memset(v, 0x3f3f3f3f, sizeof(v));
    ifstream fin("apm.in");
    fin >> n >> m;
    int x, y, c, r=0;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
    fin.close();
    H.push({0, 1});
    p[1] = -1;
    for (;!H.empty();)
    {
        int nod = H.top().second;
        int cc = H.top().first;
        H.pop();
        if (viz[nod])
            continue;
        viz[nod]=1;
        r += cc;
        if (p[nod] != -1)
            sol.push_back({p[nod], nod});
        for (auto it : G[nod])
        {
            if (viz[it.first])
                continue;

            if (v[it.first] > it.second)
            {
                v[it.first] = it.second;
                p[it.first] = nod;
                H.push({it.second, it.first});
            }
        }
    }
    ofstream fout("apm.out");
    fout << r << '\n';
    fout << sol.size() << '\n';
    for (auto it : sol)
        fout << it.first << " " << it.second << '\n';
    fout.close();
    return 0;
}