#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;
};
struct mem{
    int x, y;
};
mem b[MAX];
tata a[MAX];
int dad[MAX];
long long int rezcost  = 0;
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;
    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  dr = 0;
    for(int i = 1; i<=m; i++)
    {
        while(sef(a[i].x) != sef(a[i].y))
        {
            rezcost += a[i].cost;
            dad[sef(a[i].x)] = sef(a[i].y);
            b[++dr].x = a[i].x;
            b[dr].y = a[i].y;
        }
    }
    fout << rezcost << "\n";
    fout << dr << "\n";
    for(int i = 1; i<=dr; i++)
        fout << b[i].x << " " << b[i].y << "\n";
    return 0;
}