#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
typedef long long ll;
const ll Nmax=1e6+5, inf=1e9+5;
using pii=pair<int, int>;
struct DSU{
    vector <int> rep, s;
    int cc;
    DSU (int n){
        rep.resize(n);
        s.resize(n);
        for (int i=0; i<n; i++){
            rep[i]=i;
            s[i]=1;
        }
        cc=n;
    }
    int get_rep (int n){
        if (n==rep[n])
            return n;
        return rep[n]=get_rep(rep[n]); //path compression
    }
    int get_size(int n){
        return s[get_rep(n)];
    }
    bool same_set(int a, int b){
        return get_rep(a)==get_rep(b);
    }
    void join (int a, int b){
        int ra=get_rep(a),
            rb=get_rep(b);
        if (ra==rb)
            return;
        cc--;
        if (s[ra]>s[rb]){
            s[ra]+=s[rb];
            rep[rb]=ra;
        }
        else{
            s[rb]+=s[ra];
            rep[ra]=rb;
        }
    }
};

vector <pair<int, pii>> edge;
vector<pii> vsol;
int n, m;
int main()
{
    fin>>n>>m;
    int a, b, val;
    for (int i=0; i<m; i++){
        fin>>a>>b>>val;
        edge.pb({val, {a, b}});
    }
    sort(edge.begin(), edge.end());
    DSU dsu(n);
    int sol=0;
    for (int i=0; i<m; i++)
        if (!dsu.same_set(edge[i].se.fi, edge[i].se.se)){
            sol+=edge[i].fi;
            dsu.join(edge[i].se.fi, edge[i].se.se);
            vsol.pb(edge[i].se);
        }
    fout<<sol<<'\n';
    fout<<n-1<<'\n';
    for (auto it:vsol)
        fout<<it.fi<<' '<<it.se<<'\n';
    return 0;
}