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

#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muchies {
   int x, y, cost;
}v[NMAX], aux;
 
int viz[NMAX], n, m, c, nr;
vector<pair<int, int>> vec;
 
void citire() {
    int i;
    fin >> n;
    fin >> m;
    for(i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
}

void sortare() {
    int k = 0, i;
    while(k == 0) {
        k = 1;
        for(i = 1; i < m; i++) {
            if(v[i].cost > v[i + 1].cost) {
                aux = v[i + 1];
                v[i + 1] = v[i];
                v[i] = aux;
                k = 0;
            }
        }
    }
}
 
void kruskal() {
    int i , j, k;
    i = 1;
    for(k = 1; k < n; k++) {
        while(viz[v[i].x] == viz[v[i].y] && viz[v[i].x] != 0)
            i++;
        c += v[i].cost;
        vec.push_back(make_pair(v[i].x, v[i].y));
        nr++;
        if(viz[v[i].x] + viz[v[i].y] == 0)
            viz[v[i].x] = viz[v[i].y] = v[i].x;
        else
            if(viz[v[i].x] * viz[v[i].y] == 0)
                viz[v[i].x] = viz[v[i].y] = viz[v[i].x] + viz[v[i].y];
            else {
                for(j = 1; j <= n; j++)
                    if(viz[j] == viz[v[i].x] && j != v[i].x)
                        viz[j] = viz[v[i].y];
                viz[v[i].x] = viz[v[i].y];
            }
        i++;
    }
    fout << c << "\n" << nr << "\n";
    for (int i = 0; i < vec.size(); i++)
        fout << vec[i].second << " " << vec[i].first << "\n";
}
 
int main()
{
    citire();
    sortare();
    kruskal();
}