#include <bits/stdc++.h>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct pai{
    int p1, p2, cost;
    bool operator< (const pai &other) const{
        return cost < other.cost;
    }
};
int n, x, y, z, m;
vector<vector<int>> copii;
vector<int> radacini;
vector<pai> muchi;
bitset<1000001> f;
int main(){
    fin >> n >> m;
    copii = vector<vector<int>>(n+1);
    radacini = vector<int>(n+1);
    muchi = vector<pai>(m);
    for (int i = 0; i < m; i++){
        fin >> muchi[i].p1 >> muchi[i].p2 >> muchi[i].cost;
    }
    for (int i = 1; i <= n; i++){
        radacini[i] = i;
        copii[i].push_back(i);
    }
        
    sort(muchi.begin(), muchi.end());
    int cost_min = 0;
    for (int i = 0; i < m; i++){
        if (radacini[muchi[i].p1] != radacini[muchi[i].p2]){
            cost_min += muchi[i].cost;
            f[i] = 1;
            //fout << muchi[i].p1 << " " << muchi[i].p2 << '\n';
            if (copii[radacini[muchi[i].p1]].size() < copii[radacini[muchi[i].p2]].size()){
                x = radacini[muchi[i].p1];
                for (int &j : copii[radacini[muchi[i].p1]]){
                    copii[radacini[muchi[i].p2]].push_back(j);
                    radacini[j] = radacini[muchi[i].p2];
                }
                copii[x].clear();
            }                
            else{
                x = radacini[muchi[i].p2];
                for (int &j : copii[radacini[muchi[i].p2]]){
                    copii[radacini[muchi[i].p1]].push_back(j);
                    radacini[j] = radacini[muchi[i].p1];
                }
                copii[x].clear();
            }
        }
    }
    fout << cost_min << '\n';
    for (int i = 0; i < m; i++){
        if (f[i] == 1){
            fout << muchi[i].p1 << ' ' << muchi[i].p2 << '\n';
        }
    }
    return 0;
}