/// Kruskal
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m, suma_costurilor_muchiilor;
vector < pair < int, int > > Sol;
int *RG, *TT;
struct art { int x, y, c; } *M; // :D

int Find(int x)
{
    int y, bos = x;
    while (bos != TT[bos]) bos = TT[bos];
    while (x != TT[x])
    {
        y = TT[x];
        TT[x] = bos;
        x = y;
    }
    return bos;
}

void Unite(int x, int y)
{
    if (RG[x] < RG[y]) TT[x] = y, RG[y] += RG[x];
    else TT[y] = x, RG[x] += RG[y];
}

bool cmp(art a, art b)
{
    if (b.c < a.c) return false;
    return true;
}

int main()
{
    fin >> n >> m;
    RG = new int[n + 1]();
    TT = new int[n + 1]();
    M = new art[m + 1]();

    for (int i = 1; i <= m; i++)
        fin >> M[i].x >> M[i].y >> M[i].c;

    sort (M + 1, M + 1 + m, cmp);

    for (int i = 1; i <= n; i++)
    {
        RG[i] = 1;
        TT[i] = i;
    }

    for (int f1, f2, i = 1; i <= m; i++)
    {
        f1 = Find(M[i].x);
        f2 = Find(M[i].y);
        if (f1 != f2)
        {
            Unite(f1, f2);
            Sol.push_back( { M[i].x, M[i].y } );
            suma_costurilor_muchiilor += M[i].c;
        }
    }

    fout << suma_costurilor_muchiilor << '\n';
    fout << Sol.size() << '\n';
    for (auto it : Sol) fout << it.first << ' ' << it.second << '\n';

    return 0;
}