#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2e5 + 5;
const int MMax = 4e5 + 5;

struct Edge{
    int cost, x, y;
}v[MMax];

int G[NMax];

vector < int > ans;

inline bool cmp(const Edge &a, const Edge &b){
    return a.cost < b.cost;
}

int Group(const int x){
    if(G[x] == x) return x;
    G[x] = Group(G[x]);
    return G[x];
}

inline void Reunion(const int a, const int b){
    G[Group(a)] = Group(b);
}

int main(){
    int n, m, Total_cost;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++){
        G[i] = i;
    }
    Total_cost = 0;
    for(int i = 1; i <= m; i++){
        if(Group(v[i].x) != Group(v[i].y)){
            Total_cost += v[i].cost;
            Reunion(v[i].x, v[i].y);
            ans.push_back(i);
        }
    }
    fout << Total_cost << "\n" << n - 1 << "\n";
    for(int i = 0; i < n - 1; i++){
        fout << v[ans[i]].x << " " << v[ans[i]].y << "\n";
    }
    return 0;
}