#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;
int L[400005], ctot, 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 UNION(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){
            ctot+=E[i].cost;
            nr_muchii++;
            E[i].sel=true;
            UNION(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<<ctot<<'\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;
}