#include<bits/stdc++.h>
auto in = std::freopen("apm.in" , "r" , stdin);
auto out = std::freopen("apm.out" , "w" , stdout);
#define fast std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
int n,m;
std::vector<std::array<int,3>> weights;
int p[200005];
std::vector<int> tree[100005];
int find(int i){
    if(p[i] == i)return i;
    return p[i] = find(p[i]);
}

bool same_cc(int a, int b){
    return find(a) == find(b);
}

void unite(int a, int b){
    p[find(a)] = find(b);
}

int main(){
    fast;
    std::cin >> n >> m;
    for(int i=1;i<=n;++i)p[i] = i;
    for(int i=1;i<=m;++i){
        std::array<int,3> arr;
        std::cin >> arr[1] >> arr[2] >> arr[0];
        weights.push_back(arr);
    }
    
    std::sort(weights.begin(),weights.end());
    
    int S=0;
    std::vector<std::pair<int,int>> ans;
    for(auto f : weights){
        int a = f[1];
        int b = f[2];
        int w = f[0];

        if(!same_cc(a,b)){
            S += w;
            unite(a,b);
            tree[a].push_back(b);
            tree[b].push_back(a);
            ans.push_back({a,b});
        }
    }

    std::cout << S << '\n' << ans.size() << "\n";
    for(auto f : ans)std::cout << f.first <<' ' << f.second << "\n";
    return 0;
}