#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

struct edge{
    int a,b,c;
};

const int NMAX = 200005;
vector<int> comp[NMAX];
vector<edge> edges;
int compOfNode[NMAX];
int n,m;

void mergeComp(int a, int b) {
    for (auto i : comp[a]) {
        comp[b].push_back(i);
        compOfNode[i] = b;
    }
    comp[a].clear();
}

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

void kruskal() {
    for (int i=1;i<=n;i++) {
        compOfNode[i] = i;
        comp[i].push_back(i);
    }
    int ans = 0;
    vector<pair<int,int>> ansE;
    for (auto e : edges) {
        if (compOfNode[e.a] != compOfNode[e.b]) {
            mergeComp(compOfNode[e.a],compOfNode[e.b]);
            ans += e.c;
            ansE.push_back({e.a,e.b});
        }
    }
    fout<<ans<<'\n';
    fout<<ansE.size()<<'\n';
    for (auto e : ansE) {
        fout<<e.first<<" "<<e.second<<'\n';
    }
}

int main()
{
    fin>>n>>m;
    int x,y,c;
    for (int i=1;i<=m;i++) {
        fin>>x>>y>>c;
        edges.push_back({x,y,c});
    }
    sort(edges.begin(),edges.end(),cmp);
    kruskal();
    return 0;
}