#include <iostream>
#include <fstream>
#include <queue>

#define t top
#define p first
#define s second
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,tat[200001],su;
struct compara{
bool operator()(pair<int ,pair< int,int > >x,pair<int ,pair< int,int > >y)
{
    return x.p>y.p;
}
};
priority_queue< pair<int ,pair< int,int > > ,vector < pair<int ,pair< int,int > > >,compara >q;
queue<pair <int,int> >l;
void citire()
{   int x,y,c;
    f>>n>>m;
    while(f>>x>>y>>c){
        q.push({c,{x,y}});
    }
}
void afisare()
{    g<<su<<'\n'<<n-1<<'\n';
    while(!l.empty()){
        g<<l.front().p<<" "<<l.front().s<<'\n';
        l.pop();
    }
}
int tata(int x)
{
    if(tat[x]==x)return x;
    return tata(tat[x]);
}
void cautamuchii(){
    int x,y,nr=0,fx,fy;
    while(!q.empty())
    {
        x=q.t().s.p;
        y=q.t().s.s;
        fx=tata(x);
        fy=tata(y);
        if(fx!=fy){
        if(fx>fy)tat[fx]=fy;
        else tat[fy]=fx;
        su+=q.t().p;
        l.push({x,y});
        }
        q.pop();
    }
}
void initializare()
{
    for(int i=1;i<=n;i++)tat[i]=i;
}
int main()
{
    citire();
    initializare();
    cautamuchii();
    afisare();

    return 0;
}