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

ifstream in("apm.in");
ofstream out("apm.out");

const int MAX_SIZE = 200002;

struct edge{
    int src; ///source
    int dest; ///destination
    int cost;
};

int rang[MAX_SIZE], pred[MAX_SIZE];
vector <edge> v; ///muchiile
vector < pair<int, int> > af; ///afisare muchii

void unite(int x, int y){
    if(rang[x] > rang[y])
        pred[y] = x;
    else
        pred[x] = y;
    if(rang[x] == rang[y])
        rang[y] ++;
}

int caut(int x){
    int root, aux;
    for(root = x; root != pred[root]; root = pred[root]);

    while(x != root){
        aux = pred[x];
        pred[x] = root;
        x = aux;
    }

    return root;
}

bool comp(edge a, edge b){
    return a.cost < b.cost;
}

int kruskal(int n, int m){
    int f1, f2, x, y, z;
    int totalCost = 0;

    for(int i=1;i<=n;i++){
        pred[i] = i;
        rang[i] = 1;
    }

    sort(v.begin(), v.end(), comp);

    for(int i=0;i<m;i++){
        x = v[i].src;
        y = v[i].dest;
        z = v[i].cost;

        f1 = caut(x);
        f2 = caut(y);
        if(f1 != f2){
            unite(f1, f2);
            totalCost += z;
            af.push_back({x, y});
        }
    }

    return totalCost;
}

int main()
{
    int n, m, x, y, z, sz;

    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z; ///src, dest, cost
        v.push_back({x, y, z});
    }
    in.close();

    out<<kruskal(n, m)<<"\n"<<n - 1<<"\n";
    sz = af.size();
    for(int i=0;i<sz;i++)
        out<<af[i].second<<" "<<af[i].first<<"\n";
    out.close();

    return 0;
}