#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
fstream in("apm.in",ios::in),out("apm.out",ios::out);
const int N=1+2e6,M=1+4e6;
struct Edge{
    int x,y;
    short c;
}e[M];
int n,m,t[N],s;
struct Show{
    int x,y;
}v[N-1];
class Uf{
public:
    static void make(int x){
        t[x]=x;
    }
    static int find(int x){
        if(t[x]!=x){
            t[x]=find(t[x]);
        }
        return t[x];
    }
    static bool unite(int x, int y){
        int rx=find(x),ry=find(y);
        if(rx==ry)
            return false;
        t[ry]=rx;
        return true;
    }
};
bool cmp(Edge a, Edge b){
    return a.c<b.c;
}
int main()
{
    in>>n>>m;
    for(int i=1 ; i<=m ; i++){
        in>>e[i].x>>e[i].y>>e[i].c;
    }
    sort(&e[1],&e[m+1],cmp);
    for(int i=1 ; i<=n ; i++){
        Uf::make(i);
    }
    int nr=0;
    for(int i=1 ; i<=m && nr<n-1 ; i++){
        if(Uf::unite(e[i].x,e[i].y)){
            s+=e[i].c;
            v[++nr].x=e[i].x;
            v[nr].y=e[i].y;
        }
    }
    out<<s<<'\n'<<nr<<'\n';
    for(int i=1 ; i<=nr ; i++){
        out<<v[i].x<<' '<<v[i].y<<'\n';
    }
    return 0;
}