#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


#define MMAX 400001

using namespace std;

struct edge{
    int from, to, cost;
    friend bool operator<(edge a, edge b){
        return a.cost < b.cost;
    }
};

vector<edge> graph;

vector<pair<int, int>> solution;

int t[MMAX];


int n, m;

int cost = 0;


int find(int i){
    int k = i;
    while(t[k] > 0){
        k = t[k];
    }
    while(t[i] > 0){
        t[i] = k;
        i = t[i];
    }
    return i;

}


void merge(int set_u, int set_v){
    t[set_u] += t[set_v];
    t[set_v] = set_u;
}


void MST(){

    for(int i = 1; i <= m; i++)
        t[i] = -1;


    sort(graph.begin(), graph.end(), less<edge>());
    edge w;
    int set_u, set_v;
    for(int i = 0; i < graph.size(); i++){
        w = graph[i];
        set_u = find(w.from);
        set_v = find(w.to);
        if(set_u != set_v){
            cost += w.cost;
            solution.push_back({w.from, w.to});

            merge(set_u, set_v);
        }



    }




}


int main(){
    ifstream be("apm.in");
    ofstream ki("apm.out");

    be >> n >> m;
    edge w;
    for(int i = 0; i < m; i++){
        be >> w.from >> w.to >> w.cost;
        graph.push_back(w);
    }

    MST();

    ki << cost << '\n' << n - 1 << '\n';
    for(int i = 0; i < solution.size(); i++){
        ki << solution[i].first << " " << solution[i].second << '\n';
    }



}