#include<fstream>
#include<vector>
#include<queue>
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
int n, m, dist[200005], viz[200005], pred[200005], ctmin, nrapm;
vector<pair<int, int> > v[200005];
priority_queue < pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
struct APM{
    int first, second;
}apm[200005];
int main(){

   int i, x, y, c, nod, cost;
   f1>>n>>m;
   for(i=1; i<=m; i++){
       f1>>x>>y>>c;
       v[x].push_back({y,c});
       v[y].push_back({x,c});
   }
   dist[1]=0;
   for(i=2; i<=n; i++) dist[i]=1e9+5;
   q.push({0,1});

   while(!q.empty()){
       nod=q.top().second;
       cost=q.top().first;

       if((!viz[nod])&&(nod!=1)){
           nrapm++; apm[nrapm].first=nod; apm[nrapm].second=pred[nod]; ctmin+=cost;
       }

       viz[nod]=1;
       q.pop();

       if(dist[nod]==cost)
       for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
           if((!viz[(*it).first])&&(dist[(*it).first]> (*it).second)){
               dist[(*it).first]=(*it).second;
               q.push( {dist[(*it).first],  (*it).first});
               pred[(*it).first]=nod;
       }

   }

    f2<<ctmin<<"\n"<<nrapm<<"\n";
    for(i=1; i<=nrapm; i++)
       f2<<apm[i].first<<' '<<apm[i].second<<"\n";
    return 0;
}