#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005, M = 1999999999;
int pred[N], rang[N];
struct edge{
    int firstNode, secondNode, cost;
};
vector <edge> v;
vector <pair <int,int>> af;
bool cmp(edge a, edge b){
    return a.cost < b.cost;
}
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 rad, aux;
    for(rad=x;rad!=pred[rad];rad=pred[rad]);
    while(x != pred[x]){
        aux = pred[x];
        pred[x] = rad;
        x = aux;
    }
    return rad;
}
int kruskal(int n, int m){
    int f1, f2, rez = 0;
    for(int i=1;i<=n;i++){
        pred[i] = i;
        rang[i] = 1;
    }
    sort(v.begin(), v.end(), cmp);
    for(int i=0;i<m;i++){
        f1 = caut(v[i].firstNode);
        f2 = caut(v[i].secondNode);
        if(f1 != f2){
            unite(f1,f2);
            rez += v[i].cost;
            af.push_back({v[i].firstNode, v[i].secondNode});
        }
    }
    return rez;
}
int main()
{
    int n, m, x, y, z;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        v.push_back({x,y,z});
    }
    in.close();
    out<<kruskal(n,m)<<"\n"<<n-1<<"\n";
    for(int j=0;j<af.size();j++)
        out<<af[j].first<<" "<<af[j].second<<"\n";
    out.close();
    return 0;
}