#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
//#define int long long
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>

#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define rc(s) return cout<<s,0
#define cin fin
#define cout fout
using namespace std;

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

int n,m,x,y,par[100005],siz[100005],sum;
pii x1[100005];
vector<pi>ans;

bool cmp(pii a,pii b){
    return a.sc<b.sc;
}

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

void add(int x,int y){
    int a=finf(x);
    int b=finf(y);
    if(siz[a]<siz[b]) swap(a,b);
    siz[a]+=siz[b];
    par[b]=a;
}


int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie();cout.tie();
    cin >> n >> m;
    for(int i=1;i<=n;i++) par[i]=i;
    for(int i=1;i<=m;i++){
        cin >> x1[i].fr.fr >> x1[i].fr.sc >> x1[i].sc;
    }
    sort(x1+1,x1+m+1,cmp);
    for(int i=1;i<=m;i++){
        int v1=x1[i].fr.fr;
        int v2=x1[i].fr.sc;
        if(finf(v1)!=finf(v2)) {
            add(v1,v2);
            sum+=x1[i].sc;
            ans.pb({v1,v2});
        }
    }
    cout<<sum<<'\n'<<n-1<<'\n';
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].fr<<' '<<ans[i].sc<<'\n';
    }
}