#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;
}
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;
    i=1;
    while(k<n-1){
        if(L[v[i].x]!=L[v[i].y]){
            aux[++l].x=v[i].x;
            aux[l].y=v[i].y;
            ++k;
            ct+=v[i].z;
            nr2=L[v[i].y];
            nr1=L[v[i].x];
            for(j=1;j<=n;++j)
                if(L[j]==nr2) L[j]=nr1;
        }
        ++i;
    }
    g<<ct<<'\n'<<l<<'\n';
    for(i=1;i<=l;++i){
        g<<aux[i].x<<' '<<aux[i].y<<'\n';
    }
}
int main(){
    citire();
    apm_prim();
    return 0;
}