#include <bits/stdc++.h>
#define NMAX 200005
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");

struct muchie
{
    int x, y, c;
    bool operator() (const muchie & a, const muchie & b)
    {
        return a.c > b.c;
    }
} aux, naux ;

int Father[NMAX], LENGTH[NMAX], n, m, cost;
vector <muchie> a;
bitset <NMAX> b;
priority_queue<muchie, vector < muchie >, muchie > pr;

int Fath(int nod)
{
    if (Father[nod] == nod)
        return nod;
    Father[nod] = Fath(Father[nod]);
    return Father[nod];
}

int main()
{
    f>>n>>m;
    for (int i = 1; i <= n; i++)
        Father[i] = i;

    for (int x, y, c, i = 0; i < m; i++)
    {
        f>>x>>y>>c;
        aux.x = x;
        aux.y = y;
        aux.c = c;
        pr.push(aux);
    }

    do
    {
        aux = pr.top();
        pr.pop();
        Fath(aux.x);
        Fath(aux.y);
        if (Father[aux.x] != Father[aux.y])
        {
            int lg = LENGTH[Father[aux.x]];
            if (LENGTH[Father[aux.y] > lg])
            {
                lg = LENGTH[Father[aux.y]];
                Father[Father[aux.x]] = Father[aux.y];
            }
            else if (LENGTH[Father[aux.y]] == lg)
            {
                Father[Father[aux.y]] = Father[aux.x];
                LENGTH[Father[aux.x]]++;
            }
            else Father[Father[aux.y]] = Father[aux.x];
            a.push_back(aux);
            cost += aux.c;
        }

    }while (!pr.empty());
    g<<cost<<'\n'<<n - 1 <<'\n';
    for (int i = 0; i < a.size(); i++)
        g<<a[i].x<<' '<<a[i].y<<'\n';
    return 0;
}