#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int mini, maxi, N, M;
int h[200001], tata[200001];


struct muchie
{
    int x, y;
    short c;
};

struct compar
{
    bool operator () (muchie a, muchie b)
    {
        return a.c > b.c;
    }
};

priority_queue <muchie, vector <muchie>, compar> U;
vector <muchie> sol;

int Find(int x)
{
    int r = x;

    while(tata[r]) r = tata[r];

    int aux;

    while(x != r)
    {
        aux = tata[x];
        tata[x] = r;
        x = aux;
    }

    return r;
}

void Union(int c1, int c2)
{
    if(h[c1] > h[c2]) tata[c2] = c1;

    else
    {
        tata[c1] = c2;

        if(h[c1] == h[c2]) h[c2]++;
    }
}

int main()
{
    int i, c1, c2;
    muchie m;

    fin>>N>>M;
    for(i = 1; i <= M; ++i)
    {
        fin>>m.x>>m.y>>m.c;

        U.push(m);
    }


    int ct = 0;

    while(sol.size() < N - 1)
    {
        m = U.top();
        U.pop();

        c1 = Find(m.x);
        c2 = Find(m.y);

        if(c1 != c2)
        {
            ct += m.c;
            sol.push_back(m);

            Union(c1, c2);

        }
    }

    fout<<ct<<'\n';
    fout<<sol.size()<<'\n';

    for(i = 0; i < sol.size(); ++i)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';

    return 0;
}