//
// Created by Cristian Stern on 5/20/2019.
//

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

using namespace std;

struct Edge{
    int x, y, cost;
    Edge(int a, int b, int weight);
    Edge(){}
};

Edge::Edge(int a, int b, int weight) {
    x = a;
    y = b;
    cost = weight;
}

bool cmp(Edge a, Edge b){
    return a.cost < b.cost;
}

int find(int x, vector < int > &T){
    int R, y;
    for(R = x; R != T[R]; R = T[R]);

    while(T[x] != R){
        y = T[x];
        T[x] = R;
        x = y;
    }
    return R;
}

void unite(int x, int y, vector <int> &T, vector < int > &R){
    if(R[x] > R[y])
        T[y] = x;
    else T[x] = y;
    if(R[x] == R[y]){
        R[y]++;
    }
}



int main(){
    //ifstream f("E:\\FMI\\AG\\lab3\\date.in");
    //ofstream g("E:\\FMI\\AG\\lab3\\date.out");

    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    vector < pair < int, int > > rez;
    int x, y, cost;
    f>>n>>m;
    vector < Edge > G(m);
    vector < int > TT(n);
    vector < int > RG(n);
    for(int i = 0;i < n;i++){
        TT[i] = i;
        RG[i] = 1;
    }
    for(int i = 0;i < m;i++){
        f>>x>>y>>cost;
        x--;
        y--;
        G.emplace_back(x, y, cost);
    }
    sort(G.begin(), G.end(), cmp);
    int nr = 0;
    long long int s = 0;
    for(int i = 0;i < m;i++){
        Edge u = G[i];
        if(find(u.x, TT) != find(u.y, TT)){
            unite(find(u.x, TT), find(u.y, TT), TT, RG);
            rez.emplace_back(u.x + 1, u.y + 1);
            s += u.cost;
            nr++;
            if(nr == n - 1)
                break;
        }
    }
    g<<s<<"\n";
    g<<n-1<<"\n";
    for(auto muchie : rez)
        g<<muchie.first<<" "<<muchie.second<<"\n";

}