#include <fstream>
#include <algorithm>
#define NMax 400005
using namespace std;
struct Muchie{
    int x, y, cost;
};
Muchie v[NMax];
pair<int, int> Sol[NMax];
int Tata[NMax], Rang[NMax];
int n, m, k, costtotal;
ifstream f("apm.in");
ofstream g("apm.out");
bool Compare(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}
void citire()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].cost;
}
int Find(int nod)
{
    while(Tata[nod] != nod)
        nod = Tata[nod];
    return nod;
}
void uniune(int nod1, int nod2)
{
    if(Rang[nod1] < Rang[nod2])
    {
        Tata[nod1] = nod2;
        Rang[nod2] += Rang[nod1];
    }
    else if(Rang[nod2] < Rang[nod1])
    {
        Tata[nod2] = nod1;
        Rang[nod1] += Rang[nod2];
    }
    else
    {
        Tata[nod1] = nod2;
        Rang[nod2] += Rang[nod1];
    }   
}
void solutie()
{
    for(int i = 1; i <= m; i++)
    {
        int tx = Find(v[i].x);
        int ty = Find(v[i].y);
        if(tx != ty)
        {
            uniune(tx, ty);
            Sol[++k].first = v[i].x;
            Sol[k].second = v[i].y;
            costtotal += v[i].cost;
        }
    }
}
int main()
{
    citire();
    sort(v + 1, v + m + 1, Compare);
    for(int i = 1; i <= m; i++)
    {
        Tata[i] = i;
        Rang[i] = 1;
    }
    solutie();
    g << costtotal << endl << k << endl;
    for(int i = 1; i <= k; i++)
        g << Sol[i].first << " " << Sol[i].second << endl;
}