#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 200005
#define int long long

int x[MAXN], y[MAXN], c[MAXN];
int link[MAXN], sze[MAXN], ord[MAXN];
vector <int> vertans;
int n,m,ans;
bool comp(int i,int j)
{
    return c[i] < c[j];
}

int fnd(int x){
    while (x != link[x]) x = link[x];
    return x;
}

bool same(int a, int b){
    return fnd(a) == fnd(b);
}

void unite(int a, int b){
    a = fnd(a);
    b = fnd(b);
    if (sze[a] < sze[b]) swap(a,b);
    sze[a] += sze[b];
    link[b] = a;
}

signed main(){
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x[i] >> y[i] >> c[i];
        ord[i] = i;
    }
    for (int i = 1; i <= n; i++) link[i] = i;
    for (int i = 1; i <= n; i++) sze[i] = 1;
    sort(ord+1,ord+m+1,comp);
    for (int i = 1; i <= m; i++){
        int a = x[ord[i]];
        int b = y[ord[i]];
        if (!same(a,b)){
            unite(a,b);
            ans += c[ord[i]];
            vertans.pb(ord[i]);
        }
    }
    fout << ans << "\n";
    fout << vertans.sz << "\n";
    for (int i = 0; i < vertans.sz; i++)
        fout << y[vertans[i]] << ' ' << x[vertans[i]] << "\n";
    return 0;
}