#include <bits/stdc++.h>
#define MAX_MUCHII 400000
#define MAX_NOD 200000
using namespace std;

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

int n, m, costAPM, k;

struct muchie
{
    int x, y, c;
}M[MAX_MUCHII + 2];

int tata[MAX_NOD + 2], h[MAX_NOD + 2], sol[MAX_NOD + 2];

void init()
{
    for(int i = 1; i <= n; i++)
        tata[i] = i, h[i] = 1;
}

int Find(int x)
{
    if(tata[x] == x)
        return x;
    tata[x] = Find(tata[x]);
    return tata[x];
}

void Union(int x, int y)
{
    int a = Find(x), b = Find(y);

    if(h[a] < h[b])
        tata[a] = b;
    else
    {
        tata[b] = a;
        if(h[a] == h[b])
            ++h[a];
    }
}

void Citire()
{
    fin >> n >> m;

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

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

void Afisare()
{
    fout << costAPM << '\n' << k << '\n';

    for(int i = 1; i <= k; i++)
        fout << M[i].x << " " << M[i].y << '\n';
}

int main()
{
    Citire();

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

    init();

    int a, b;
    for(int i = 1; i <= m && k <= n-1; i++)
    {
        a = Find(M[i].x);
        b = Find(M[i].y);

        if(a != b)
        {
            sol[k++] = i;
            costAPM += M[i].c;
            Union(M[i].x, M[i].y);
        }
    }

    Afisare();
    return 0;
}