#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;

int n,m;
int parent[NMAX], cost_total, nr;


struct muchie{
    int nod1, nod2, cost;
    bool sel;
}E[NMAX];

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int FIND(int x){
    if (parent[x]==x) return x;
    parent[x]=FIND(parent[x]);
    return parent[x];
}

bool check(int a, int b){
    return FIND(a) == FIND(b);
}

void UNION(int a, int b){
    int A = FIND(a);
    int B = FIND(b);

    parent[A]=B;
}

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

    for (int i=1;i<=m;i++){
        if (check(E[i].nod1, E[i].nod2) == false){
            E[i].sel=true;
            cost_total += E[i].cost;
            nr++;
            UNION (E[i].nod1, E[i].nod2);
        }
    }
}

int main(){
    f>>n>>m;
    for (int i=1;i<=m;i++){
        f>>E[i].nod1>>E[i].nod2>>E[i].cost;
    }

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

    Kruskal();

    g<<cost_total<<'\n';
    g<<nr<<'\n';
    for (int i=1;i<=m;i++){
        if (E[i].sel==true) g<<E[i].nod1<<" "<<E[i].nod2<<'\n';
    }
}