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

using namespace std;

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

int n, m, suma_costurilor_muchiilor;
vector < int > Sol;
int RG[200010], TT[200010];
struct art { int x, y, c; } M[400010];

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

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

    return 0;
}