#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int N, M;


int findDis(int elem, vector<pair<int, int>> &multimi)
{
    int radacina = elem;
    while(multimi[radacina].first != radacina) {
        radacina= multimi[radacina].first;
    }
    while(multimi[elem].first != radacina) {
        int auxiliar = multimi[elem].first;
        multimi[elem].first = radacina;
        elem = auxiliar;
    }
    return radacina;
}

void unionDis(const int x, const int y, vector<pair<int, int>> &multimi)
{
    int radX = findDis(x, multimi), radY = findDis(y, multimi);

    if(multimi[radX].second > multimi[radY].second) {
        multimi[radX].second = multimi[radX].second + multimi[radY].second;
        multimi[radY].first = radX;
        multimi[radY].second = multimi[radX].second;
    }
    else{
        multimi[radY].second = multimi[radY].second + multimi[radX].second;
        multimi[radX].first = radY;
        multimi[radX].second = multimi[radY].second;
    }
}


void Kruskal(vector<pair<int, pair<int, int>>> muchii)
{
    vector<pair<int, int>> multimi(N + 1, {0, 0});
    vector<pair<int,int>> rez(1, {-1, -1});
    int costTotal = 0;

    for(int i = 1; i <= N; ++i) {
        multimi[i] = {i, 1};
    }

    sort(muchii.begin() + 1, muchii.end());

    for(int i = 1; i <= M && rez.size() < N; ++i) {
        if( findDis(muchii[i].second.first, multimi) != findDis(muchii[i].second.second, multimi) ){
            unionDis(muchii[i].second.first, muchii[i].second.second, multimi);
            costTotal = costTotal + muchii[i].first;
            rez.push_back({muchii[i].second.first, muchii[i].second.second});
        }
    }

    fout << costTotal << "\n";
    for(int i = 1; i < rez.size(); ++i)
        fout << rez[i].first << " " << rez[i].second << "\n";
}
int main()
{
    fin >> N >> M;
    vector<pair<int, pair<int, int>>> muchii(M + 1);
    for(int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii[i] = {c, {x, y}};
    }
    Kruskal(muchii);
    return 0;
}