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

struct Muchie
{
    int x,y;
    int c;
    friend bool operator >(const Muchie& a, const Muchie& b);
};

bool operator >(const Muchie&a, const Muchie& b)
{
    return a.c > b.c;
}

int N,Mu;
vector<Muchie> apm;
int nrsol,cmin;
int ta[NMAX], ra[NMAX];
priority_queue<Muchie,vector<Muchie>,greater<Muchie> > M;

int Find(int x);
void Union(int x, int y);
void Citire();
void Rezolva();
void Afisare();

int main()
{
    Citire();
    Rezolva();
    Afisare();
    return 0;
}

void Citire()
{
    Muchie a;
    fin>>N>>Mu;
    for(int i = 1; i<=Mu; i++)
    {
        fin>>a.x>>a.y>>a.c;
        M.push(a);
    }
}

void Rezolva()
{
    for(int i = 1; i<=N;i++)
        ta[i] = i,ra[i] = 1;

    Muchie a;
    int rx,ry;
    while(nrsol<N-1)
    {
        a = M.top();
        M.pop();

        rx = Find(a.x);
        ry = Find(a.y);

        if(rx!= ry)
        {
            Union(rx,ry);
            cmin += a.c;
            apm.push_back(a);
            nrsol++;
        }
    }
}

void Afisare()
{
    fout<<cmin<<'\n';
    fout<<apm.size()<<'\n';
    for(int i = 0; i<apm.size(); i++)
        fout<<apm[i].x<<" "<<apm[i].y<<'\n';
}

int Find(int x)
{
    int r, y;

    //urc in arbore spre nodul ce ponteaza spre el insusi
    for(r = x; ta[r]!=r; r = ta[r]);

    for(;ta[x]!=x;)
    {//compresie
        y = ta[x];
        ta[x] = r;
        x = y;
    }
    return r;
}

void Union(int x,int y)
{
    if(ra[x] < ra[y])
        ta[x] = y;
    else
        ta[y] = x;

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