#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,L[200005],l;
struct vec{
    int x,y,z;
}v[NMAX],aux[NMAX];
int cmp(struct vec a,struct vec b){
    return a.z<b.z;
}
void citire(){
    f>>n>>m;
    int i;
    for(i=1;i<=m;++i)
        f>>v[i].x>>v[i].y>>v[i].z;
}
int grupa(int i)
{
    if (L[i] == i) return i;
    L[i] = grupa(L[i]);
    return L[i];
}
void reuniune(int i,int j)
{
    L[grupa(i)] = grupa(j);
}
void apm_prim(){
    sort(v+1,v+1+m,cmp);
    int ct=0,i=1,k;
    L[v[i].x]=1;
    L[v[i].y]=1;
    ct+=v[i].z;
    aux[++l].x=v[i].x;
    aux[l].y=v[i].y;
    for(k=1;k<=n-2;++k){
        i=1;
        while(L[v[i].x]==L[v[i].y]) i++;
        ct+=v[i].z;
        aux[++l].x=v[i].x;
        aux[l].y=v[i].y;
        if(L[v[i].x]) L[v[i].y]=1;
        else L[v[i].x]=1;
    }
    g<<ct<<'\n'<<l<<'\n';
    for(i=1;i<=l;i++)
        g<<aux[i].x<<' '<<aux[i].y<<'\n';
}
void apm_kruskal(){
    sort(v+1,v+1+m,cmp);
    int i,ct=0,k=0,j,nr1,nr2;
    for(i=1;i<=n;++i)
        L[i]=i;
    for(i=1;i<=m;i++){
        if(grupa(v[i].x)!=grupa(v[i].y)){
            aux[++l].x=v[i].x;
            aux[l].y=v[i].y;
            ct+=v[i].z;
            reuniune(v[i].x,v[i].y);
        }
    }
    g<<ct<<'\n'<<l<<'\n';
    for(i=1;i<=l;++i){
        g<<aux[i].x<<' '<<aux[i].y<<'\n';
    }
}
int main(){
    citire();
    apm_kruskal();
    return 0;
}