#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 200003

using namespace std;

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

int nr[DIM],T[DIM],N,M,x,y,z;
int Sol;
struct link{
    int x,y,z;
};
vector <link> v;
vector <pair <int, int > > tree;
int root(int x){
    int ret = x ;

    while(T[ret] != ret)
        ret = T[ret];

    int current = x ;
    while(T[current] != current){
        int aux = T[current];
        T[current] = ret;
        current = aux ;
    }
    return ret;

}

void connect( int x, int y){
    int a = root(x);
    int b = root(y);
    if(nr[b] < nr[a]){
        nr[a] += nr[b];
        T[b] = a;
    }
    else{
        nr[b] += nr[a];
        T[a] = b;
    }
}
int cmp(link a,link b){
    return a.z<b.z;
}
int main(){

    fin >> N >> M ;

    for ( int i = 1 ; i <= N ;i++ ){
        T[i] = i;
        nr[i] = 1;
    }

    for(int i = 1; i <= M; i ++){
        link edge;
        fin >> edge.x >> edge.y >> edge.z ;
        v.push_back(edge);
    }

    sort(v.begin(),v.end(),cmp);

    for(int i = 0; i < v.size(); i ++){
        int a = v[i].x;
        int b = v[i].y;

        if(root(a) != root(b)){
            connect(a , b);
            tree.push_back(make_pair(a , b));
            Sol += v[i].z;
        }
    }

    fout << Sol << "\n" << N - 1 << "\n" ;

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

    fin.close();fout.close();

    return 0;
}