#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

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

vector<pair<pair<int, int>, int>>muchii;
vector<int>tata(200001);
vector<int>h(400001);
vector<pair<int,int>>solutie;
int n, m, x, y, c, cost_final;

void initializare(int x){
    tata[x]=h[x]=0;
}

bool sortare(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){
    return a.second < b.second;
}

int reprezentant(int x){
    while(tata[x]!=0)
        x=tata[x];
    return x;
}

void reuneste(int x, int y){
    int rx= reprezentant(x), ry= reprezentant(y);
    if(h[rx]>h[ry]){
        tata[ry]=rx;
    }
    else{
        tata[rx]=ry;
        if(h[rx]==h[ry])
            h[ry]=h[ry]+1;
    }
}

int main() {
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        initializare(i);
    for(int i=0; i<m; i++){
        fin>>x>>y>>c;
        muchii.push_back(make_pair(make_pair(x, y),c));
    }
    sort(muchii.begin(), muchii.end(), sortare);
    for(int i=0; i<m; i++){
        x=muchii[i].first.first;
        y=muchii[i].first.second;
        c=muchii[i].second;
        if(reprezentant(x) != reprezentant(y)){
            reuneste(x,y);
            cost_final=cost_final+c;
            solutie.push_back(make_pair(x,y));
        }
    }
    fout<<cost_final<<'\n'<<solutie.size()<<'\n';
    for(int i=0; i<solutie.size(); i++){
        fout<<solutie[i].first<<" "<<solutie[i].second<<'\n';
    }
    return 0;
}