#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("kruskal.in");
ofstream g("kruskal.out");
const int NMAX = 10e5+1;

int tata[NMAX+1];
int ad[NMAX+1];

void generare(int n){
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        ad[i]=1;
    }
}
int caut(int nod){
    if(nod==tata[nod])
        return nod;
    return tata[nod]=caut(tata[nod]);
}
void unire(int a, int b){
    a=caut(a);
    b=caut(b);
    if(a!=b){
        if(ad[a]<ad[b])
            swap(a,b);
        tata[b]=a;
        ad[a]+=ad[b];
    }
}
/// Paduri de multimi disjuncte implementate anterior
struct muchie{int e,r, cost;};
muchie G[NMAX+1];
int n,m;
queue<pair<int, int>> Q;


int cmp(muchie a, muchie b){
    return (a.cost<b.cost);
}
int minimuuuum=0;

int kruskal(){
    int cost_minim  = 0;
    sort(G+1, G+m+1, cmp);
    int nrmuchii=0;
    for(int i=1;i<=m&&nrmuchii<n-1;i++)
    {
        int e=caut(G[i].e);
        int r=caut(G[i].r);
        if(e!=r){
            nrmuchii++;
            cost_minim += G[i].cost;
            minimuuuum++;
            Q.push(make_pair(G[i].e,G[i].r));
            unire(e,r);
        }
    }
    return cost_minim;
}

int main()
{
    f>>n>>m;
    generare(n);
    for(int i=1;i<=m;i++)
        f>>G[i].e>>G[i].r>>G[i].cost;

    g<<kruskal()<<'\n'<<minimuuuum<<'\n';
    while(!Q.empty())
    {
        g<<Q.front().first<<' '<<Q.front().second<<'\n';
        Q.pop();
    }
    return 0;
}