#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

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

int n;
int m;
int father[100010];
int rang[100010];
int s;
int counter;

struct edge  {

    int x;
    int y;
    int cost;

};

vector <edge> edges;
vector <edge> rez;

int fin(int x) {

    if(father[x] == 0) {
        return x;
    } else {
        return fin(father[x]);
    }

}

int uni (int x, int y) {

    int rooty;
    int rootx;
    rooty = fin(y);
    rootx = fin(x);
    if(rootx == rooty) {
        return 0;
    }
    if(rang[rootx] > rang[rooty]) {
        father[rooty] = rootx;
    } else {
        if(rang[rootx] < rang[rooty]) {
            father[rootx] = rooty;
        } else {
            father[rootx] = rooty;
            rang[rooty]++;
        }
    }

}

int kruskal () {

    for(int i = 0; i < edges.size(); i++) {
        if(fin(edges[i].x) != fin(edges[i].y)) {
            uni(edges[i].x, edges[i].y);
            edge e;
            e.x = edges[i].x;
            e.y = edges[i].y;
            rez.push_back(e);
            s = s + edges[i].cost;
            counter++;
            if(counter == n - 1) {
                break;
            }
        }
    }
    out << s << endl;
    out << n - 1 << endl;
    for(int i = 0; i < rez.size(); i++) {
        out << rez[i].y << " " << rez[i].x << endl;
    }

}

int main() {

    in >> n;
    in >> m;

    for(int i = 0; i < m; i++) {
        edge e;
        in >> e.x;
        in >> e.y;
        in >> e.cost;
        edges.push_back(e);
    }
     sort(edges.begin(), edges.end(), [](edge a, edge b) {
        return a.cost < b.cost;
    });

    kruskal();
}