//Kruskal O(n logn)
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[200005];
int h[200005];
int findr(int x){
    int r = x;
    while(r != t[r]) r = t[r];
    int y = x;
    t[x] = r;
    while(y != r){
        int d = t[y];
        t[y] = r;
        y = d;
    }
    return r;
}
void unire(int x, int y){
    int rx = findr(x);
    int ry = findr(y);
    if(h[rx] < h[ry]) t[x] = y;
    else{
        if(h[rx] > h[ry]) t[y] = x;
        else{
            t[rx] = ry;
            h[ry]++;
        }
    }
}
struct muchie{
    int u,v,c;
};
int n,m;
muchie e[400005];
struct edge{
    int x,y;
    edge(int _x, int _y){
        x = _x;
        y = _y;
    }
};
vector <edge> vec;
bool comp(muchie a, muchie b){
    return a.c <= b.c;
}
void kruskal(){
    int rez = 0;
    for(int i = 1; i <= m; i++){
        if(findr(e[i].u) != findr(e[i].v)){
            unire(e[i].u,e[i].v);
            rez += e[i].c;
            vec.push_back( edge(e[i].v, e[i].u) );
        }
    }
    fout << rez << "\n" << n - 1 << "\n";
    for(auto x : vec) fout << x.x << " " << x.y << "\n";
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++) t[i] = i;
    for(int i = 1; i <= m; i++) fin >> e[i].u >> e[i].v >> e[i].c;
    sort(e + 1, e + m + 1, comp);
    kruskal();
    return 0;
}