#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int NMAX = 200000;
const int MMAX = 400000;

struct edge
{
    int from, to, cost;

    bool operator < (const edge other) const
    {
        return cost < other.cost;
    }
};

int N, M;
edge v[2 * MMAX + 5];

int dad[NMAX + 5], rnk[NMAX + 5];
long long apm;
vector <edge> apmEdges;

int Root(int node)
{
    int initNode = node, p = dad[node];

    while(node != p)
    {
        node = p;
        p = dad[p];
    }

    dad[initNode] = p;
    return p;
}

void Join(int p, int q)
{
    if(rnk[p] < rnk[q])
        dad[p] = q;
    else if(rnk[p] > rnk[q])
        dad[q] = p;
    else
        rnk[p]++, dad[q] = p;
}

int main()
{
    fin >> N >> M;

    int x, y, c, k = 0;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;

        v[++k].from = x;
        v[k].to = y;
        v[k].cost = c;

        v[++k].from = y;
        v[k].to = x;
        v[k].cost = c;
    }

    sort(v + 1, v + k + 1);

    for(int i = 1; i <= N; i++)
        dad[i] = i;

    k = 0;
    for(int i = 1; k < N - 1; i++)
    {
        int p = v[i].from;
        int q = v[i].to;

        int pp = Root(p);
        int qq = Root(q);

        if(pp != qq)
        {
            k++;
            apm += v[i].cost;
            apmEdges.push_back(v[i]);
            Join(pp, qq);
        }
    }

    fout << apm << '\n' << N - 1 << '\n';

    for(auto it : apmEdges)
        fout << it.from << ' ' << it.to << '\n';

    return 0;
}