#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

// algoritmul lui kruskal
// folosind paduri de multimi disjuncte

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int N,M,nrmuchii,costarb;
int dad[200010];

struct muchie {
    int x,y,cost;
}v[400010],rez[400010];

bool cmp(muchie,muchie);
int find_dad(int);

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort (v+1,v+M+1,cmp); // ordonam muchiile crescator in functie de cost
    FOR (i,1,N) {
        dad[i]=i;
    }
    int i=1;
    while (nrmuchii<N-1) {
        while (find_dad(v[i].x)==find_dad(v[i].y)) { // cat timp nodurile muchiei se afla in acelasi arbore mergem mai departe
            ++i;
        }
        int dadx=find_dad(v[i].x);
        int dady=find_dad(v[i].y);
        if (dadx<dady) { // unim cei doi arbori gasiti introducand nodurile din arborele cu indice mai mare in cel cu indice mai mic
            dad[dady]=dadx;
        }
        else {
            dad[dadx]=dady;
        }
        costarb+=v[i].cost;
        rez[++nrmuchii]=v[i];
        ++i;
    }
    g<<costarb<<'\n'<<nrmuchii<<'\n';
    FOR (i,1,nrmuchii) {
        g<<rez[i].x<<' '<<rez[i].y<<'\n';
    }
    f.close();g.close();
    return 0;
}

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

int find_dad(int x) {
    int aux=x;
    while (dad[aux]!=aux) {
        aux=dad[aux];
    }
    int radacina=aux;
    while (x!=radacina) {
        aux=dad[x];
        dad[x]=radacina;
        x=aux;
    }
    return radacina;
}