#include<bits/stdc++.h>

using namespace std;

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

int n , m;
struct Iris{
    int x  , y , cost;
};
int parent[200001] , sz[200001];

inline bool cmp(Iris a , Iris b){
    return a.cost < b.cost;
}

Iris graf[400001];

inline int find(int x){
    if(parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

inline void unite(int a , int b){
    a = find(a);
    b = find(b);
    if(a != b){
        if(sz[a] < sz[b]) swap(a , b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}

int main(){
    fin >> n >> m;
    for(int i = 1 ; i <= m ; i++){
        int x , y , cost;
        fin >> x >> y >> cost;
        graf[i] = {x , y , cost};
    }
    for(int i = 1 ; i <= n ; i++) parent[i] = i , sz[i] = 1;
    sort(graf + 1 , graf + m + 1 , cmp);
    vector<pair<int , int>> rez;
    long long sum = 0;
    for(int i = 1 ; i <= m ; i++){
        int x = graf[i].x;
        int y = graf[i].y;
        if(find(x) != find(y)){
            int parentx = find(x);
            int parenty = find(y);
            unite(parentx , parenty);
            sum += graf[i].cost;
            rez.push_back({x , y});
        }
    }
    fout << sum << '\n';
    fout << rez.size() << '\n';
    for(auto i : rez) fout << i.first <<" "<< i.second << '\n';
}