/// KRUSKAL (N log M cred)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<cassert>
#include<vector>
using namespace std;

ifstream in("apm.in");

const int N = 200001;
const int M = 400001;

struct edge{
    int from;
    int to;
    int cost;

    bool operator<(const edge& other){
        return cost < other.cost;
    }

    friend ostream& operator <<(ostream &out, const edge &x){
        out<<""<<x.from<<" -> "<<x.to<<", cost = "<<x.cost<<"\n";
        return out;
    }
};

struct node{
    static int n_nodes;
    int boss_index;
    int index;
};

int n_colors = 0;
vector<edge> solution;
edge edges[M];
node nodes[N];
int n,m,crtEdge = 0;

int getBiggestBoss(int index){
    /// Find Big Boss
    int visitedNodes[N], n_visited = 1;
    visitedNodes[0] = index;

    int bigBoss_index = index;
    while(nodes[bigBoss_index].boss_index != bigBoss_index){
        bigBoss_index = nodes[bigBoss_index].boss_index;
        visitedNodes[n_visited++] = bigBoss_index;
    }

    /// Optimisation
    for(int i=0; i<n_visited; ++i)
        nodes[visitedNodes[i]].boss_index = bigBoss_index;

    return bigBoss_index;
}

bool edge_links_two_forests(edge x){
    int boss_1 = getBiggestBoss(x.from);
    int boss_2 = getBiggestBoss(x.to);

    //cout<<x.from<<"'s big boss is "<<boss_1<<"\n";
    //cout<<x.to<<"'s big boss is "<<boss_2<<"\n";
    //for(int i=1; i<=n; ++i) cout<<i<<" "; cout<<"\n";
    //for(int i=1; i<=n; ++i) cout<<getBiggestBoss(i)<<" "; cout<<"\n";
    //for(int i=1; i<=n; ++i) cout<<nodes[i].boss_index<<" "; cout<<"\n";


    return boss_1 != boss_2;
}

void link_forests(edge x){
    int to_biggestBoss_index = getBiggestBoss(x.to);
    int from_biggestBoss_index = getBiggestBoss(x.from);

    nodes[to_biggestBoss_index].boss_index = from_biggestBoss_index;
}

void linkEdge(){
    /// Find the smallest edge that
    while(crtEdge < m && !edge_links_two_forests(edges[crtEdge])){
        ++crtEdge;
        //cout<<"crtEdge = "<<crtEdge<<"\n";
    }

    /// Don't call this function if we cannot pick an edge
    assert(crtEdge < m);

    /// Link the two forests
    solution.push_back(edges[crtEdge]);
    link_forests(edges[crtEdge]);

    //cout<<"Linking nodes "<<edges[crtEdge].from<<" and "<<edges[crtEdge].to<<"\n";
    ++crtEdge;
}

int main()
{
    /// Input
    freopen("apm.out","w",stdout);

    in>>n>>m;
    for(int i=0; i<m; ++i){
        int index_1, index_2, cost;
        in>>index_1>>index_2>>cost;

        edges[i].cost = cost;
        edges[i].from = index_1;
        edges[i].to = index_2;
    }

    /// Init
    for(int i=1; i<=n; ++i){
        nodes[i].index = i;
        nodes[i].boss_index = i;
    }

    /// Solve
    sort(edges, edges+m);
    //for(int i=0; i<m; ++i) cout<<edges[i];

    for(int i=1; i<n; ++i)
        linkEdge();

    /// Print
    int sum = 0;
    for(auto &x : solution)
        sum += x.cost;
    cout<<sum<<"\n";
    cout<<n-1<<"\n";
    for(auto &x : solution)
        cout<<x.from<<" "<<x.to<<"\n";

    return 0;
}