#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Nmax=2e5+5;

struct DSU {
    int dad[Nmax];
    void init(int n) {
        for (int i=1; i<=n; ++i) dad[i]=i;
    }
    int find(int node) {
        if (dad[node]==node) return node;
        return dad[node]=find(dad[node]);
    }
    void merge(int u, int v) {
        dad[find(u)]=find(v);
    }
} dsu;

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin>>n>>m;
    vector<array<int,3>> edges(m);
    for (auto &[c,x,y]:edges) cin>>x>>y>>c;
    sort(edges.begin(),edges.end());
    dsu.init(n);
    ll ans=0;
    vector<pair<int,int>> apm;
    for (auto [c,x,y]:edges) {
        if (dsu.find(x)!=dsu.find(y)) {
            dsu.merge(x,y);
            ans+=c;
            apm.push_back({x,y});
        }
    }
    cout<<ans<<'\n'<<apm.size()<<'\n';
    for (auto [x,y]:apm) cout<<x<<' '<<y<<'\n';
    return 0;
}