#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 200005;

int n, m, sum, c;

struct mu {
    int f, t, w;
};

vector < mu > v, rez;

int p[nmax], rnk[nmax];

bool comp (mu u, mu uu)
{
    return u.w < uu.w;
}

int root(int nod)
{
    while (nod != p[nod])
    {
        p[nod] = p[p[nod]];
        nod = p[nod];
    }

    return nod;
}

void unite(int x, int y)
{
    if (rnk[x] > rnk[y])
        p[y] = x;
    else
        p[x] = y;

    if (rnk[x] == rnk[y])
        rnk[y]++;
}

void Kruskal()
{
    for (mu e : v)
    {
        int t = e.t;
        int f = e.f;

        int rootF = root(f), rootT = root(t);

        if (rootT != rootF)
        {
            rez.push_back({f, t, 0});
            sum += e.w;
            unite(rootF, rootT);
        }
    }


}

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

    for (int i = 1; i <= m; i++)
    {
        int f, t, w;

        fin >> f >> t >> w;

        v.push_back({f, t, w});
    }

    sort(v.begin(), v.end(), comp);

    for (int i = 1; i <= n; i++)
    {
        rnk[i] = 1;
        p[i] = i;
    }

    Kruskal();


    fout << sum << '\n' << rez.size() << '\n';

    for (int i = 0; i < rez.size(); i++)
        fout << rez[i].f << ' ' << rez[i].t << '\n';



    fin.close();
    fout.close();
    return 0;
}