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

using namespace std;

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

const int M = 400001;
const int N = 200001;

int n, m, t[N], cost;
bool selectat[N];

struct muchie{
    int x, y, c;
}v[M];

int radacina(int x)
{
    if(t[x] == x)
        return x;
    t[x] = radacina(t[x]);
    return t[x];
}

bool comp(muchie a, muchie b)
{
    return (a.c < b.c);
}

int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
        in>>v[i].x>>v[i].y>>v[i].c;
    for(int i=1; i<=n; i++)
        t[i] = i;

    sort(v+1, v+m+1, comp);

    for(int i=1; i<=m; i++)
    {
        if(radacina(v[i].x) != radacina(v[i].y))
        {
            selectat[i] = true;
            cost += v[i].c;
            t[radacina(v[i].y)] = radacina(v[i].x);
        }
    }
    out<<cost << "\n" << n - 1 << "\n";
    for (int i = 1; i <= m; i++)
    {
        if (selectat[i]) out << v[i].y << " " << v[i].x << "\n";
    }
    return 0;
}