#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct Muchie {
    int x;
    int y;
    int cost;
};
int n,m,x,y,cost,s,nr,c;
vector<int>t(n+1,0);
vector<int>h(n+1,1);
vector<Muchie>v,rez;
bool cmp(Muchie a, Muchie b) {
    return a.cost<b.cost;
}
int Find(int x){
    while(t[x]!=x){
        x=t[x];
    }
    return x;
}
void Union(int x, int y)
{
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(h[x]<h[y])
            t[x]=y;
        else if(h[x]>h[y])
            t[y]=x;
        else{
            t[y]=x;
            h[x]++;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;
        v.push_back({x,y,c});
    }
    for(int i=1;i<=n;i++)
        t[i]=i;
    sort(v.begin(),v.end(),cmp);
    for(auto muchie:v){
        if(Find(muchie.x)!=Find(muchie.y))
        {
            cost+=muchie.cost;
            nr++;
            s+=muchie.cost;
            rez.push_back(muchie);
            Union(muchie.x,muchie.y);
        }
    }
    g<<s<<"\n"<<nr<<"\n";
    for(auto muchie:rez){
        g<<muchie.x<<" "<<muchie.y<<"\n";
    }
    return 0;
}