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

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

long long n, m, k = 0, s[400005], f[400005], c[400005], ind[400005], R[400005], sol[400005], costMin = 0;

bool ordCost(int x, int y)
{
    return c[x] < c[y];
}

int reprez(int x)
{
    if(R[x] == x)
        return x;
    R[x] = reprez(R[x]);
    return R[x];
}

void reuniune(int x, int y)
{
    R[reprez(x)] = reprez(y);
}

int main()
{
    in>>n>>m;
    for(long long i = 1; i <= m; i++)
    {
        in>>s[i]>>f[i]>>c[i];
        ind[i] = i;
    }
    for(long long i = 1; i <= n; i++)
        R[i] = i;
    sort(ind + 1, ind + m + 1, ordCost);
    for(long long i = 1; i <= m; i++)
    {
        if(reprez(s[ind[i]]) != reprez(f[ind[i]]))
        {
            costMin += c[ind[i]];
            reuniune(s[ind[i]], f[ind[i]]);
            k++;
            sol[k] = ind[i];
        }
    }
    out<<costMin<<"\n";
    out<<n-1<<"\n";
    for(long long i = 1; i <= k; i++)
        out<<s[sol[i]]<<" "<<f[sol[i]]<<"\n";
    return 0;
}