#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define x first
#define y second
#define pi pair <int, int>
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define pb push_back
const ll mod = 1e9 + 7;
vector <int> c;
int x, z, cost;
int n, m;
vector <int> nod[200001];
vector <pair<pi, int>> v;
vector <int> a;
int viz[200001];
ll ans;

bool cs16(pair<pi, int> a, pair<pi, int> b){
    return (a.y<=b.y);
}

void dfs(int cul, int varf, int ctrl){
    viz[varf]=ctrl;
    c[varf]=cul;
    for(int j=0; j<nod[varf].sz; j++){
        {if(viz[nod[varf][j]]!=ctrl) dfs(cul, nod[varf][j], ctrl);}
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin>>n>>m;
    v.resize(m+1);
    c.resize(m+1);
    for(int i=1; i<=m; i++){
        cin>>x>>z>>cost;
        v[i]={{x, z}, cost};
    } int curr=0;
    sort(v.begin()+1, v.end(), cs16);
    ///for(int i=1; i<=m; i++) cout<<v[i].x.x<<" "<<v[i].y<<endl;
    for(int i=1; i<=m; i++){
        if(c[v[i].x.x]==0 || c[v[i].x.y]==0){
            if(c[v[i].x.x]==c[v[i].x.y]){
                curr++;
                c[v[i].x.x]=curr; c[v[i].x.y]=curr;
                a.pb(i); ans+=(v[i].y)*1LL;
            }
            else{
                if(c[v[i].x.x]==0) c[v[i].x.x]=c[v[i].x.y];
                else c[v[i].x.y]=c[v[i].x.x];
                a.pb(i); ans+=(v[i].y)*1LL;
            } nod[v[i].x.x].pb(v[i].x.y); nod[v[i].x.y].pb(v[i].x.x);
        }
        else if(c[v[i].x.x]!=c[v[i].x.y]){
            if(c[v[i].x.x]>c[v[i].x.y])
            {dfs(c[v[i].x.y], v[i].x.x, c[v[i].x.x]); viz[v[i].x.y]=c[v[i].x.x];}
            else
            {dfs(c[v[i].x.x], v[i].x.y, c[v[i].x.y]); viz[v[i].x.x]=c[v[i].x.y];}
            a.pb(i); nod[v[i].x.x].pb(v[i].x.y); nod[v[i].x.y].pb(v[i].x.x);
            ans+=(v[i].y)*1LL; ///dbg(ans);
        }
    } cout<<ans<<'\n';
      cout<<a.sz<<'\n';
    for(int i=0; i<a.sz; i++) cout<<v[a[i]].x.x<<" "<<v[a[i]].x.y<<'\n';
}