#include <algorithm>
#include <fstream>

using namespace std;

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

#define N 200001
#define M 400001

int n, m;
int X[M], Y[M], cost[M];
int v[M];
int t[N];
int ok[M];

int multime(int x)
{
    if(t[x] == 0)
        return x;
    t[x] = multime(t[x]);
    return t[x];
}

inline void reuneste(int x, int y)
{
    x = multime(x);
    y = multime(y);
    if(x != y)
        t[y] = x;
}

inline bool cmp(int i1, int i2)
{
    return cost[i1] < cost[i2];
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        X[i] = x;
        Y[i] = y;
        cost[i] = c;
        v[i] = i;
    }

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

    int sum = 0;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        x = X[v[i]];
        y = Y[v[i]];
        c = cost[v[i]];
        x = multime(x);
        y = multime(y);
        if(x != y)
        {
            ok[v[i]] = 1;
            sum += c;
            reuneste(x, y);
        }
    }
    out << sum << '\n' << n - 1 << '\n';

    for(int i = 1; i <= m; i++)
        if(ok[v[i]])
            out << X[v[i]] << ' ' << Y[v[i]] << '\n';
    return 0;
}