/*
    Programmer : Alexandru Olteanu
*/
#include<bits/stdc++.h>
using namespace std;
// GCC Optimizations
// #pragma GCC optimize("Ofast");
// #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt")
// #pragma GCC target("abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize(3)
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse")
// #pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-ftree-pre")
// #pragma GCC optimize("-ftree-vrp")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("unroll-loops")
// Useful
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define FastEverything  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define HighPrecision cout<<fixed<<setprecision(17);
typedef long long ll;
typedef pair<int,int> pii;
ll const mod=1000000007LL;
ll const mod2 = 100000000LL;
ll const md=998244353LL;
ll mypowr(ll a,ll b, ll mod1) {ll res=1;if(b<0)b=0;a%=mod1; assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a%mod1;a=a*a%mod1;}return res;}
ll mypow(ll a,ll b) {ll res=1;if(b<0)b=0;assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()

ifstream in("apm.in");
ofstream out("apm.out");
#define cin in
#define cout out

const ll infll = 9e18;
const int inf = 2e9;
const ll maxn = 5e4 + 5;

/*
    Template created by Alexandru Olteanu
*/
vector<pair<ll, int>> graph[maxn];
int p[maxn];
vector<pii> res;
int cost_final = 0;
template<typename A>
struct SpanningTree {

    vector<tuple<A, int, int>> edge;

    int find(int x){
        if(!p[x])return (p[x] = x);
        return ((x == p[x]) ? x : (p[x] = find(p[x])));
    }

    void merge(int x, int y){
        p[x] = y;
        return;
    }

    void push_graph(A cost, int first, int second){
        tuple<A, int, int> l;
        l = {cost, first, second};
        edge.pb(l);
        return;
    }
    void build_tree(){
        sort(all(edge));
        ll n = (ll)edge.size();
        for(ll i = 0; i < n; ++i){
            int x = find(get<1>(edge[i]));
            int y = find(get<2>(edge[i]));
            A cost = get<0>(edge[i]);
            if(x == y)continue;
            graph[get<1>(edge[i])].pb({cost, get<2>(edge[i])});
            graph[get<2>(edge[i])].pb({cost, get<1>(edge[i])});
            res.pb({get<1>(edge[i]), get<2>(edge[i])});
            cost_final += cost;
            merge(x, y);
        }
 
        return;
    }
};
int main()
{
    FastEverything
    HighPrecision

    int test = 1;
    // cin >> test;
    for (int tt = 1; tt <= test; ++tt) {
        int n, m;
        cin >> n >> m;
        SpanningTree<int> st;
        for (int i = 1; i <= m; ++i) {
            int x, y, cost;
            cin >> x >> y >> cost;
            st.push_graph(cost, x, y);
        }
        st.build_tree();
        cout << cost_final << '\n';
        cout << res.size() << '\n';
        for (auto u : res) {
            cout << u.fi << " " << u.se << '\n';
        }

    }

    return 0;
}