#include <fstream>
#include <vector>
#include <algorithm>
#define N 200000
#define M 400000

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie{
    int x, y, c;
};

int CT;
int n, m;
int t[N + 1];
vector <Muchie> mch;
vector <pair<int,int>> rasp;

int parinte(int copil){
    int par = copil;
    while(par != t[par])
        par = t[par];
    while(copil != par){
        int aux = t[copil];
        t[copil] = par;
        copil = aux;
    }
    return par;
}

void uneste(int cop1, int cop2){
    t[parinte(cop1)] = parinte(cop2);
}

bool cmp(Muchie a, Muchie b){
    return a.c < b.c;
}

void kruskal(){
    for(int i = 1; i < n; i++)
        t[i] = i;
    sort(mch.begin(), mch.end(), cmp);
    for(int j = 0; j < m; j++){
        if(parinte(mch[j].x) != parinte(mch[j].y)){
            uneste(mch[j].x, mch[j].y);
            CT += mch[j].c;
            //pair <int,int> p
            rasp.push_back({mch[j].x, mch[j].y});
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        mch.push_back({x, y, c});
    }
    kruskal();
    fout << CT << '\n';
    fout << n - 1 << '\n';
    for(int i = 0; i < n - 1; i++)
        fout << rasp[i].first << ' ' << rasp[i].second << '\n';
    return 0;
}