#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
#define MAX 100000
ifstream fin("apm.in");
ofstream fout("apm.out");
struct tata{
    int x, y, cost;
};

tata a[MAX];
int dad[MAX];
inline bool cmp(tata e, tata f)
{
    return e.cost < f.cost;
}
int sef(int i)
{
    if(dad[i] != i)
        dad[i] = sef(dad[i]);
    return dad[i];
}
int main()
{
    int n, m, rezcost = 0;
    fin >> n >> m;
    for(int i = 1; i<=m; i++)
    {
        fin >>  a[i].x >> a[i].y >> a[i].cost;
    }
    sort(a + 1, a + m + 1, cmp);

    for(int i = 1; i<=n; i++)
        dad[i] = i;
    int j, z = 0;
    for(int i = 1; i<=m; i++)
    {
        while(sef(a[i].x) != sef(a[i].y))
        {
            rezcost += a[i].cost;
            z++;
            dad[sef(a[i].x)] = sef(a[i].y);
        }
    }
    fout << rezcost << "\n";
    fout << z << "\n";
    for(int i = 1; i<n; i++)
        fout << a[i].x << " " << a[i].y << "\n";
    return 0;
}