//
//  main.cpp
//  kruskal
//
//  Created by Alexandru Bâgu on 5/28/14.
//  Copyright (c) 2014 OkieDokie. All rights reserved.
//

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMax 200001
int colors[NMax];

struct edge {
    int i, j, weight;
    int *ic, *jc;
    int attached;
};
vector<edge*> edges;
int cmp(edge* a, edge* b){
    return a->weight < b->weight;
}

int main(int argc, const char * argv[])
{
    ifstream input("apm.in");
    int N, M;
    input>>N>>M;
    for(int i = 0; i <= N; i++)
        colors[i] = i;
    for(int i = 0; i < M; i++) {
        edge *e = new edge;
        input>>e->i>>e->j>>e->weight;
        e->ic = colors + e->i;
        e->jc = colors + e->j;
        e->attached = 0;
        edges.push_back(e);
    }
    input.close();
    sort(edges.begin(), edges.end(), cmp);
    int apm_edges = 0, apm_cost = 0;
    for(int i = 0; i < edges.size(); i++) {
        edge *a = edges[i];
        if(*a->ic != *a->jc)
        {
            a->attached = 1;
            
            int color = *a->jc;
            for(int j = 0; j <= N; j++)
                if(colors[j] == color)
                    colors[j] = *a->ic;
            
            apm_edges++;
            apm_cost += a->weight;
        }
    }
    ofstream output("apm.out");
    output<<apm_cost<<"\n"<<apm_edges<<"\n";
    for(int i = 0; i < edges.size(); i++) {
        edge *a = edges[i];
        if(a->attached) {
            output<<a->j<<" "<<a->i<<"\n";
        }
        delete a;
    }
    edges.clear();
    return 0;
}