#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;

int n,m;
int T[NMAX];
long long ctot;
int 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 (T[x]==x) return x;
    T[x]=FIND(T[x]);
    return T[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);

    T[A]=B;
}

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

    for (int i=1;i<=m;i++){
        if (check(E[i].nod1, E[i].nod2)==false){
            E[i].sel=true;
            ctot+=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<<ctot<<'\n';
    g<<nr<<'\n';
    for (int i=1;i<=m;i++){
        if (E[i].sel==true) g<<E[i].nod1<<" "<<E[i].nod2<<'\n';
    }
}