/**
    -----------------------------------------------------------------------



    -----------------------------------------------------------------------
    futasi ido:

    -----------------------------------------------------------------------
**/
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

struct edge {
    int u, v, w;
};

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

void beolvas(int &n, int &m, vector<edge> &edges) {
    ifstream fin("apm.in");
    fin >> n >> m;
    edges.resize(m);
    for(int i=0; i<m; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
}

void kruskal(int n, int m, vector<edge> &edges) {
    sort(edges.begin(), edges.end(), cmp);
    vector<int> id(n+1);
    vector<edge> res;
    int cost=0;

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

    for(int i=0; i<m; i++) {
        if(id[edges[i].u]!=id[edges[i].v]) {
            cost+=edges[i].w;
            res.push_back(edges[i]);

            int regi=id[edges[i].u];
            int uj=id[edges[i].v];
            for(int i=1; i<=n; i++) {
                if(id[i]==regi) {
                    id[i]=uj;
                }
            }
        }
    }

    ofstream fout("apm.out");
    fout << cost << '\n' << res.size() << '\n';
    for(auto it : res) {
        fout << it.u << ' ' << it.v << '\n';
    }
}

int main() {
    int n, m;
    vector<edge> edges;
    beolvas(n, m, edges);
    kruskal(n, m, edges);
    return 0;
}