#include<bits/stdc++.h>
using namespace std;

string numeFisier="apm";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout

#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll


int t, n, m, k, a[300010], q, l, r;
vector<pii> g[200010];

bool v[200010];

int32_t main(){
INIT
cin>>n>>m;
int mn=1e18; pii e;
for(int i=1, u, v, w; i<=m; i++){
    cin>>u>>v>>w;
    if(w<mn){
        mn=w;
        e=mp(u, v);
    }
    g[u].pb(mp(v, w));
    g[v].pb(mp(u, w));
}

vector<pii> edg;

int sum=0;
v[e.ft]=v[e.sc]=true;
sum+=mn;
edg.pb(e);

multiset<pair<int, pii>> ms;
for(pii pr:g[e.ft]){
    ms.insert(mp(pr.sc, mp(e.ft, pr.ft)));
}

for(pii pr:g[e.sc]){
    ms.insert(mp(pr.sc, mp(e.sc, pr.ft)));
}

while(!ms.empty()){
    auto it=ms.begin();
    int w=it->ft, u=it->sc.ft, u2=it->sc.sc;
    if(!v[u2]){
        v[u2]=true;
        sum+=w;
        for(auto pr:g[u2]){
            ms.insert(mp(pr.sc, mp(u2, pr.ft)));
        }
        edg.pb(mp(u, u2));
    }
    ms.erase(it);
}


cout<<sum<<"\n";
cout<<edg.size()<<"\n";
for(auto pr:edg){
    cout<<pr.ft<<" "<<pr.sc<<"\n";
}


return 0;
}