#include <bits/stdc++.h>

using namespace std;

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

int const penis=2e5+1;

tuple <int,int,int> edges[2*penis]; ///cost, origin, destination

int N, M, C, O, D, root[penis], origin, destination, totalcost;

vector <pair<int,int>> solutions;

int getRoot(int nod){
    if(root[nod]==nod)
        return nod;
    root[nod]=getRoot(root[nod]);
    return root[nod];
}

int main()
{
    fin>>N>>M;
    for(int i=0; i<M; i++){
        fin>>O>>D>>C;
        edges[i]=make_tuple(C,O,D);
    }
    for(int i=0; i<N; i++)
        root[i]=i;
    sort(edges,edges+M);
    for(int i=0; i<M; i++){
        tie(C,O,D)=edges[i];
        origin=getRoot(O);
        destination=getRoot(D);
        if(origin!=destination){
            root[destination]=root[origin];
            totalcost+=C;
            solutions.push_back(make_pair(O,D));
        }
    }
    fout<<totalcost<<"\n";
    fout<<solutions.size()<<"\n";
    for(auto it:solutions){
        fout<<it.first<<" "<<it.second<<"\n";
    }
}