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


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 total_cost_minim;

int find_root(int i)
{
    if (tata[i] == i) return i;
    tata[i] = find_root(tata[i]);
    return tata[i];
}

void unionsets(int i,int j)
{
    tata[find_root(i)] = find_root(j);
}

void read()
{
    muchie mm;
    fin>>n>>m;
    for(int i=0;i<m;i++)
        {fin>>mm.c1>>mm.c2>>mm.cost;
         PQ.push(mm);}
    for(int i=1;i<=n;i++) tata[i]=i;
}

void kruskal()
{
    int comp1,comp2;
    muchie mm;
    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
        }
    }
}

void print()
{

    fout<<total_cost_minim<<"\n"<<n-1<<"\n";
    for (int i=0;i<n-1;++i)
        fout<<apm[i].c1<<" "<<apm[i].c2<<"\n";
}
int main()
{
    read();
    kruskal();
    print();
    fin.close();
    fout.close();
    return 0;
}