#include <bits/stdc++.h>  /** 2fat2code a.k.a grandmixer420  **/
#define ll long long
#define all(a) (a).begin(), (a).end()
#define sz() size()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
using namespace std;

int n,m,x,y,z,tot,cp[200005],s[200005];
vector<pair<int,int>>nod[200005];
vector<pair<pair<int,int>,int>>t;
vector<pair<int,int>>ans;

freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);

int grup(int x){
    while(x!=cp[x]) x=cp[x];
    return x;
}

void uniune(int x,int y,int z){
 //   cout << x << ' ' << y << ' ' << grup(x) << ' ' << grup(y) << endl;
    cp[grup(y)]=grup(x);
    tot+=z;
    ans.push_back({x,y});

}


bool cmp(pair<pair<int,int>,int>a,pair<pair<int,int>,int>b){
    return a.sc<b.sc;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> x >> y >> z;
        nod[x].push_back({y,z});
        nod[y].push_back({x,z});
        t.push_back({{x,y},z});
    }
    for(int i=1;i<=n;i++) cp[i]=i;
    sort(all(t),cmp);
    int cnt=n-1LL,ind=-1LL;
    while(cnt!=0){
        ind++;
        x=t[ind].fr.fr,y=t[ind].fr.sc,z=t[ind].sc;
        if(grup(x)==grup(y)) continue;
        else{
            if(s[x]<=s[y]) swap(x,y);
            uniune(x,y,z);
            cnt--;
        }
    }
    cout<<tot<<endl<<n-1LL<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].fr<<' '<<ans[i].sc<<endl;
    }
}