#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n, m, scm;
vector < int > Sol;
int *RG, *TT;
struct art { int x, y, c; } *M;

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)
{
    return (a.c < b.c);
}

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(i);
            scm += M[i].c;
        }
    }

    fout << scm << '\n' << Sol.size() << '\n';
    for (auto it : Sol) fout << M[it].x << ' ' << M[it].y << '\n';

    return 0;
}