#include <algorithm>
#include <fstream>

#define N 200001
#define M 400001
using namespace std;

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

int n, m;
int t[N], pred[N];

int lst[N], vf[M], vf2[M], cost[M], urm[M], nvf = 0;
int muchii[M];

int rez[M], nrez = 0;

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

    t[x] = multime(t[x]);
    return t[x];
}

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];
}

void kruskal()
{
    int s = 0;

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        x = vf2[muchii[i]];
        y = vf[muchii[i]];
        c = cost[muchii[i]];

        x = multime(x);
        y = multime(y);

        if(x != y)
        {
            reuneste(x, y);
            pred[y] = x;
            s += c;
            rez[++nrez] = i;
        }
    }

    out << s << '\n' << n - 1 << '\n';

    for(int i = 1; i <= nrez; i++)
    {
        int x, y;
        x = vf2[muchii[rez[i]]];
        y = vf[muchii[rez[i]]];

        out << x << ' ' << y << '\n';
    }
}

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

    for(int i = 1; i <= m; i++)
    {
        muchii[i] = i;

        int x, y, c;
        in >> x >> y >> c;

        vf[++nvf] = y;
        vf2[nvf] = x;
        cost[nvf] = c;
        urm[nvf] = lst[x];
        lst[x] = nvf;
    }

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

    kruskal();
    return 0;
}