/// PRIM (N LOG M)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<cassert>
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 bigBoss;
    // int boss;
    int color = -1;
    int index = -1;
};

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

bool edge_links_two_forests(edge x){
    int firstColor = nodes[x.from].color;
    int secondColor = nodes[x.to].color;

    if(firstColor == -1 || secondColor == -1) return true;
    else return firstColor != secondColor;
}

void link_forests(edge x){
    int firstColor = nodes[x.from].color;
    int secondColor = nodes[x.to].color;

    if(firstColor == -1 && secondColor == -1){
        nodes[x.from].color = nodes[x.to].color = ++n_colors;
    }
    else if(firstColor != -1 && secondColor != -1){
        for(int i=1; i<=n; ++i)
            if(nodes[i].color == secondColor)
                nodes[i].color = firstColor;
    }
    else if(firstColor == -1 && secondColor != -1){
        nodes[x.from].color = secondColor;
    }
    else if(firstColor != -1 && secondColor == -1){
        nodes[x.to].color = firstColor;
    }

}

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;
    }

    /// 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;
}