#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 200001
#define MMAX 400001
using namespace std;

struct muchie{
int c1;
int c2;
int cost;
friend bool operator >(const muchie&,const muchie&);
};

bool operator>(const muchie& m1,const muchie&m2)
{
    return m1.cost>m2.cost;
}

int n,m;
priority_queue<muchie, vector<muchie>, greater<muchie> > PQ;
vector<muchie> apm;
int tata[NMAX];
int rg[NMAX];
int total_cost_minim;

int find_root(int x)
{
    int root=x;
    while(tata[root]) root=tata[root];
    int y=x,aux;
    while(y!=root)
        {
            aux=tata[y];
            tata[y]=root;
            y=aux;
        }
    return root;
}

void unionsets(int x,int y)
{
    if(rg[x]>rg[y]) tata[y]=x;
    else {
        tata[x]=y;
        if(rg[x]==rg[y]) rg[y]++;
    }
}

int main()
{
    muchie mi;
    ifstream fin("apm.in");
    fin>>n>>m;
    for(int i=0;i<m;i++)
        {fin>>mi.c1>>mi.c2>>mi.cost;
         PQ.push(mi);}
    fin.close();
    muchie mm;
    int comp1,comp2;
    while(apm.size()<n-1)
    {
        mm=PQ.top();
        PQ.pop();
        comp1=find_root(mm.c1);
        comp2=find_root(mm.c2);//det comp conexe din care fac parte extrem muchiei selectate
        if(comp1!=comp2) //nu formeaza cicluri
        {
            total_cost_minim+=mm.cost;//selectez muchia
            apm.push_back(mm);
            unionsets(comp1,comp2);//unific comp conexe ale extremitatilor
        }


    }
    ofstream fout("apm.out");
    fout<<total_cost_minim<<endl;
    fout<<n-1<<endl;
    for(int i=0;i<n-1;i++)
        fout<<apm[i].c1<<" "<<apm[i].c2<<endl;
    fout.close();
    return 0;
}