#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();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
ifstream fin("apm.in"); ofstream fout("apm.out");
#define cin fin
#define cout fout
int n, m;
vector<vector<pii>> g;
vector<pii> mc;
bool v[200010];

int apm(){
int c=0;
multiset<pair<int, pii>> h;
h.insert(mp(0, mp(0, 1) ) );

while(!h.empty()){
while( v[(*h.begin()).sc.sc]==true ){
    h.erase(h.begin());
} if(h.empty()){break;}
pair<int, pii> f; f=*(h.begin()); h.erase(h.begin());
c+=f.ft;
v[f.sc.sc]=true;

if(f.sc.sc!=1){
    mc.pb(mp(f.sc.ft, f.sc.sc) );
}


for(int i=0; i<g[f.sc.sc].size(); i++){
if(v[g[f.sc.sc][i].ft]==true ){continue;}
h.insert(mp(g[f.sc.sc][i].sc, mp(f.sc.sc, g[f.sc.sc][i].ft) ) );
}



}





return c;
}





int32_t main(){
INIT
cin>>n>>m; g.resize(n+5);
for(int i=0; i<m; i++){
    int x, y, c;
    cin>>x>>y>>c;
    g[x].pb(mp(y, c));
    g[y].pb(mp(x, c));
}
int res=apm();
cout<<res<<"\n"<<mc.size()<<"\n";
for(int i=0; i<mc.size(); i++){
    cout<<mc[i].ft<<" "<<mc[i].sc<<"\n";
}






return 0;
}