#include <iostream>
#include <fstream>
#include <algorithm>
#define L 400005

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m, suma, t[L], rg[L], nm;
bool used[L];
pair <int, int> p[L];
struct muchii{
    int a, b, c;
}v[L];
bool comp(muchii x, muchii y){
    return x.c<y.c;
}
void read(){
    in >> n >> m;
    for (int i=1;i<=m;++i){
        int x, y, z;
        in >> x >> y >> z;
        v[i].a=x;
        v[i].b=y;
        v[i].c=z;
    }
    sort(v+1, v+m+1, comp);

    for (int i=1;i<=n;++i){
        t[i]=i;
        rg[i]=1;
    }

}
int Find(int nod){
    while (t[nod]!=nod)
        nod=t[nod];
    return nod;
}
void unite(int x, int y){
    if (rg[x]>rg[y])
        t[y]=x;
    else if (rg[y]>rg[x])
        t[x]=y;
    else if (rg[x]==rg[y]){
        t[x]=y;
        ++rg[y];
    }


}

void kruskal(){
    for (int i=1;i<=m;++i){
        int t_a=Find(v[i].a);
        int t_b=Find(v[i].b);
        if (t_a!=t_b){
            unite(t_a, t_b);
            p[++nm].first=v[i].b;
            p[nm].second=v[i].a;
            suma+=v[i].c;
        }
    }
}

int main()
{
    read();
    kruskal();
    out << suma << "\n" << nm << "\n";
    for (int i=1;i<=nm;++i)
        out << p[i].first << " " << p[i].second << "\n";

    return 0;
}