#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
int L[400005],tot,nr_muchii;
struct muchie {
    int x,y,cost;
    bool sel;
}E[400005];
bool cmp(muchie a, muchie b){
    return a.cost<b.cost;
}
int boss(int x){
    if (L[x]==x) return x;

    L[x]=boss(L[x]);
    return L[x];
}
bool check(int a,int b){
    return (boss(a)==boss(b));
}
void uniune(int a,int b){
    int A=boss(a);
    int B=boss(b);

    L[A]=B;
}
void Kruskal(){
    for (int i=1;i<=n;i++) L[i]=i;

    sort(E+1,E+m+1,cmp);

    for (int i=1;i<=m;i++){
        if (check(E[i].x, E[i].y)==false){
            tot+=E[i].cost;
            nr_muchii++;
            E[i].sel=true;
            uniune(E[i].x, E[i].y);
        }
    }
}
int main(){
    f>>n>>m;
    for (int i=1;i<=m;i++)
        f>>E[i].x>>E[i].y>>E[i].cost;

    Kruskal();

    g<<tot<<'\n';
    g<<nr_muchii<<'\n';
    for (int i=1;i<=m;i++)
        if (E[i].sel==true) g<<E[i].x<<" "<<E[i].y<<'\n';

    return 0;
}