#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define pb push_back
#define pii  pair<int,int>
#define piii pair<int,pair<int,int>>

using namespace std;

struct DSU{
    int n;
    vector<int> root;
    DSU(int n): n(n){
        root = vector<int>(n+1);
        for(int i=1;i<=n;i++) root[i]=i;
    }
    int getRoot(int x){
        if(root[x]==x) return x;
        return root[x] = getRoot(root[x]);
    }
    bool join(int x, int y){
        x = getRoot(x);
        y = getRoot(y);
        if(x==y) return false;
        root[x] = y;
        return true;
    }
};

int32_t main(){

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);

    int n, m, x, y, w;
    cin>>n>>m;
    vector<piii> edges;
    vector<pii> final_edges;
    for(int i=0;i<m;i++){
        cin>>x>>y>>w;
        edges.pb({w,{x,y}});
    }
    sort(edges.begin(),edges.end());
    DSU tree(n);
    int final_cost = 0;
    for(int i=0;i<m;i++){
        if(tree.join(edges[i].second.first,edges[i].second.second)){
            final_cost+=edges[i].first;
            final_edges.eb(edges[i].second.first, edges[i].second.second);
        }
    }
    int nr = final_edges.size();
    cout<<final_cost<<'\n';
    cout<<nr<<'\n';
    for(int i = 0;i<nr;i++)
        cout<<final_edges[i].first<<' '<<final_edges[i].second<<'\n';
    return 0;
}