#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int Mmax = 4e5 + 5, Nmax = 2e5 + 5;
struct ura{
    int a, b, c;
}v[Mmax];

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

int n, m, sef[Nmax], siz[Nmax];


int findSef( int x)
{
    if ( sef[x] == x )
        return x;
    return findSef(sef[x]);
}
void join( int a, int b)
{
    int sefA = findSef(a);
    int sefB = findSef(b);

    if ( sefA == sefB )
        return ;

    if ( siz[sefA] > siz[sefB] )
    {
        siz[sefA] += siz[sefB];
        sef[sefB] = sefA;
    }
    else
    {
        siz[sefB] += siz[sefA];
        sef[sefA] = sefB;
    }
}
int main()
{
    fin >> n >> m;
    int i, j;
    for ( i = 1; i <= m; ++i )
    {
        int a, b, c;
        fin >> a >> b >> c;
        v[i] = {a, b, c};

    }
    sort( v + 1, v + m + 1, cmp);

    for ( i = 1; i <= n; ++i )
    {
        sef[i] = i;
        siz[i] = 1;
    }

    int costMin = 0;
    vector <pair<int, int>> solution;
    for ( i = 1; i <= m; ++i )
    {
        if ( findSef(v[i].a) != findSef(v[i].b))
        {
            costMin += v[i].c;
            join(v[i].a, v[i].b);
            solution.push_back({v[i].a, v[i].b});
        }

    }

    fout << costMin << '\n' << solution.size() << '\n';
    for ( i = 0; i < solution.size(); ++i )
        fout << solution[i].first << " " << solution[i].second << '\n';

    return 0;
}