#include <bits/stdc++.h>

using namespace std;

///ifstream f ("prim.in");
///ofstream g ("prim.out");

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

struct muchie
{
    int i, j, cost;
};

const int NMAX = 400000;
vector <muchie> M[NMAX + 5], REZ;

bool adaugat[NMAX + 5];

struct cmp
{
    bool operator() (const muchie & x, const muchie & y) const {
        return x.cost > y.cost;
    }
};

priority_queue <muchie, vector<muchie>, cmp> pq;

long long COST;

void adaugare_pq(int nod)
{
    adaugat[nod] = 1;
    for(auto muchii: M[nod])
    {
        if(adaugat[muchii.j] == 0)
            pq.push(muchii);
    }
}

void parcurgere_pq(int n)
{
    while(!pq.empty())
    {
        if(adaugat[pq.top().i] == 1 && adaugat[pq.top().j] == 1)
        {
            pq.pop();
        }
        else
        {
            REZ.push_back(pq.top());
            COST += pq.top().cost;
            muchie MuchieNoua = pq.top();
            pq.pop();
            if(adaugat[MuchieNoua.i] == 1)
            {
                adaugare_pq(MuchieNoua.j);
            }
            else
            {
                adaugare_pq(MuchieNoua.i);
            }
        }
    }
}

int main()
{
    int n, m, i, x, y, c;
    f >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        M[x].push_back({x, y, c});
        M[y].push_back({y, x, c});
    }
    adaugare_pq(1);
    parcurgere_pq(n);
    g << COST << "\n" << n - 1 << "\n";
    for(x = 0; x < n - 1; ++x)
    {
        g << REZ[x].i << " " << REZ[x].j << "\n";
    }
    return 0;
}