#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

vector <pair<int, int> > v[200001];
vector <pair<int, int> > mfinale;
priority_queue <pair<int, pair<int, int> > > myheap;


int radacina(int tata[], int x){
    while (x!=tata[x])    {
        tata[x]=tata[tata[x]];
        x=tata[x];
    }
    return x;
}

void reuniune(int tata[], int l[], int x, int y){
    if (l[radacina(tata, x)] < l[radacina(tata, y)]){
        tata[radacina(tata, x)] = tata[radacina(tata, y)];
    }
    else{
        tata[radacina(tata, y)] = tata[radacina(tata, x)];
        l[radacina(tata, x)]++;
    }
}

bool diferite(int tata[], int l[], int x, int y){
    if (radacina(tata, x)==radacina(tata, y))
        return false;
    return true;
}

int main(){
    int n, m, x, y, cost;
    fin>>n>>m;

    vector <int> dist(n+1, 200001);
    vector <int> viz(n+1);
    int tata[n+1], l[n+1];
    for (int i = 1; i <= n; i++){
        tata[i] = i, l[i] = 1;
    }

    for (int i = 1; i <= m; i++){
        fin>>x>>y>>cost;
        myheap.push(make_pair(-cost, make_pair(x, y)));
    }

    cost=0;
    int nrMuchii=0;

    while (!myheap.empty() && nrMuchii < n-1){
        pair <int, pair<int, int> > it = myheap.top();
        int x = it.second.first;
        int y = it.second.second;
        myheap.pop();

        if (!diferite(tata, l, x, y)){
            continue;
        }

        reuniune(tata, l, x, y);

        cost -= it.first;
        mfinale.push_back(it.second);
    }

    fout<<cost<<"\n";
    fout<<n-1<<"\n";

    for (int i = 0; i < (int)mfinale.size(); i++){
        fout<<mfinale[i].first<<" "<<mfinale[i].second<<"\n";
    }

    return 0;
}