#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define mmax 400005
#define nmax 200005

using namespace std;

struct graf {
    int x, y, cost;
} G[mmax];

int n, m, cost;
int tata[nmax], nr[nmax];
vector < pair<int, int> > sol;

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

int root(int x) {
    if (tata[x] == x)
        return x;
    return root(tata[x]);
}

int main() {
    
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> G[i].x >> G[i].y >> G[i].cost;
    
    sort(G+1, G+m+1, cmp);
    
    for (int i = 1; i <= n; i++)
        tata[i] = i, nr[i] = 1;
    
    for (int i = 1; i <= m; i++) {
        
        int r1 = root(G[i].x);
        int r2 = root(G[i].y);
    
        if (r1 == r2)
            continue;
        
        if (nr[r1] >= nr[r2]) {
            tata[r2] = r1;
            nr[r1] += nr[r2];
        } else {
            tata[r1] = r2;
            nr[r2] += nr[r1];
        }
        
        cost += G[i].cost;
        
        sol.push_back(make_pair(G[i].y, G[i].x));
        
    }
    
    fout << cost << "\n";
    fout << sol.size() << "\n";
    for (int i = 0; i < sol.size(); i++)
        fout << sol[i].first << " " << sol[i].second << "\n";
    
    fin.close();
    fout.close();
    
    return 0;
}