#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

struct muchie
{
    int i, j, c;
    friend bool operator >(const muchie& a, const muchie& b)
    {
        return a.c > b.c;
    }
};

int n, m, cost;
priority_queue<muchie, vector<muchie>, greater<muchie> > M;
vector<muchie> sol;
int CC[200001];

void citire()
{
    muchie mm;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> mm.i >> mm.j >> mm.c;
        M.push(mm);
    }
}

void afis()
{
    g << cost << '\n' << n - 1 << '\n';
    for(unsigned i = 0; i < sol.size(); i++)
        g << sol[i].i << ' ' << sol[i].j << '\n';
}

int grupa(int i)
{
    if(CC[i] == 0)
        return i;
    CC[i] = grupa(CC[i]);
    return CC[i];
}

void Kruskal()
{
    unsigned n1 = n - 1;
    while(sol.size() < n1)
    {
        muchie mm = M.top();
        M.pop();
        int g1 = grupa(mm.i);
        int g2 = grupa(mm.j);
        if(g1 != g2)
        {
            cost += mm.c;
            CC[g1] = g2;
            sol.push_back(mm);
        }
    }
}

int main()
{
    citire();
    Kruskal();
    afis();
    return 0;
}