#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <fstream>

#include <iomanip>
#include <cassert>

#include <random>
#include <chrono>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ull = unsigned long long;
using ll = long long;

//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()

#define YES cout << "YES\n"
#define NO cout << "NO\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rangerng(int l, int r){
    return uniform_int_distribution<>(l, r)(rng);
}

////////////////////////////////////////////////////////////////////////////////////

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

const int NMAX = 4e5;

struct E{
    int a, b, c;

    bool operator < (const E &other) const {
        return c < other.c;
    }
};

vt <E> edges;

namespace DSU{
    int par[NMAX + 1];

    void init(int n){
        for(int i = 1; i <= n; i++){
            par[i] = i;
        }
    }

    int Find(int x){
        if(x == par[x]){
            return x;
        }
        return x = Find(par[x]);
    }

    void Join(int x, int y){
        x = Find(x);
        y = Find(y);
        
        if(x == y){
            return;
        }

        par[x] = y;
    }
}

void solve(){
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;

        E ee;
        ee.a = a, ee.b = b, ee.c = c;

        edges.pb(ee);
    }

    sort(all(edges));

    vt <pii> sol;

    int min_cost = 0;

    DSU::init(n);

    for(int i = 1; i <= m; i++){
        int a = edges[i - 1].a;
        int b = edges[i - 1].b;
        int c = edges[i - 1].c;

        //cout << "!! " << a << ' ' << b << ' ' << c << '\n';

        if(DSU::Find(a) != DSU::Find(b)){
            DSU::Join(a, b);
            min_cost += c;
            sol.pb(pii(a, b));
        }
    }

    fout << min_cost << '\n';
    fout << sz(sol);
    for(auto x : sol){
        fout << x.fr << ' ' << x.sc << '\n';
    }
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    //cin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}

/*
*/