#include <bits/stdc++.h>

using namespace std;

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

struct edge
{
    int i, j, w;
};

struct cmp{
    bool operator()(const edge x, const edge y) const
    {
        return x.w > y.w;
    }
};

vector <edge> vecini[200001], mst;
priority_queue <edge, vector <edge>, cmp> pq;
bitset <200001> pus;
int n, m, total;

int main(){
    f>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x, y, w;
        f>>x>>y>>w;
        vecini[x].push_back({x, y, w});
        vecini[y].push_back({y, x, w});
    }

    pus[1] = 1;
    for (auto e : vecini[1])
        pq.push(e);

    while (!pq.empty() and mst.size() < n - 1)
    {
        edge muchie = pq.top();
        pq.pop();

        if (pus[muchie.j] == 0)
        {
            pus[muchie.j] = 1;
            mst.push_back(muchie);
            total += muchie.w;

            for (auto e : vecini[muchie.j])
                if (pus[e.j] == 0)
                    pq.push(e);
        }
    }
    g<<total<<'\n'<<mst.size()<<'\n';
    for (auto e : mst)
        g<<e.i<<" "<<e.j<<'\n';
}