#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, sol;
bool viz[200005];
vector<pair<int, int>> G[200005];
vector<pair<int, int>> sol_muchii;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> q;
void adaugare(int nod)
{
    viz[nod] = 1;
    for (auto &nod2: G[nod])
        if (!viz[nod2.second])
        {
            pair<int, pair<int, int>> val = {nod2.first, {nod2.second, nod}};
            q.push(val);
        }
}
void prelucrare()
{
    adaugare(1);
    while (!q.empty())
    {
        pair<int, pair<int, int>> nod = q.top();
        q.pop();
        if (viz[nod.second.first])
            continue;
        adaugare(nod.second.first);
        sol += nod.first;
        sol_muchii.push_back(nod.second);
    }
}
int main() 
{
    f >> n >> m;
    int x, y, c;
    for (int i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        G[x].push_back({c, y});
        G[y].push_back({c, x});
    }
    prelucrare();
    g << sol << '\n' << sol_muchii.size();
    for (auto &muchie: sol_muchii)
        g << '\n' << muchie.first << ' ' << muchie.second;
    return 0;
}