#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

#define nmax 100005
int tata[nmax];
int rang[nmax];
int cost;
vector <pair <int, pair<int, int>>> G;
vector < pair < int, int >> muchii;

int radacina(int nod){
    if(nod == tata[nod]){
        return nod;
    }

    return tata[nod] = radacina(tata[nod]);
}

void uneste(int x, int y){
    if(rang[x] < rang[y]){
        tata[x] = y;
    }
    else{
        tata[y] = x;
        if(rang[x] == rang[y])
            rang[y]++;
    }
}

void kruskal(int n, int m){
    for(int i = 1; i <= n; ++i){
        tata[i] = i;
        rang[i] = 1;
    }

    sort(G.begin(), G.end());

    for(int i = 0; i < m; i++){
        int a = G[i].second.first;
        int b = G[i].second.second;

        int rad1 = radacina(a);
        int rad2 = radacina(b);

        if(rad1 != rad2){
            uneste(rad1, rad2);
            muchii.push_back({a,b});
            cost+=G[i].first;
        }
    }
}


int main()
{
    int n, m, c;
    fin >> n >> m;


    for(int i = 0; i < m; i++){
        int x, y;
        fin >> x >> y >> c;

        G.push_back({c, {x, y}});
    }

    kruskal(n, m);

    fout << cost << '\n';
    fout << muchii.size() << '\n';
    for(auto it : muchii){
        fout << it.first << " " << it.second << '\n';
    }

    return 0;
}