#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000005
#define nmax 200005
#define mmax 400005
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
int n, m, dist[nmax], nrmuc, pred[nmax], cost, viz[nmax];
vector <pair<int, int> > v[nmax];
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
struct muchii
{
    int x, y;
}muc[mmax];
void citire()
{
    int i, x, y, c;
    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});
    }
}
void solutie()
{
   ///dist[i]=dist min de la un varf al apm-ului la nodul i
   int i, vfmin, ct, co, vec;
   dist[1]=0;
   for(i=2; i<=n; i++) dist[i]=inf;
   q.push({0,1});

   while(!q.empty())
   {
       vfmin=q.top().second;
       ct=q.top().first;
       q.pop();

      if((vfmin!=1)&&(!viz[vfmin]))
       {
           nrmuc++;muc[nrmuc].x=pred[vfmin]; muc[nrmuc].y=vfmin;
           cost+=ct;
       }
       viz[vfmin]=1;

       for(auto it=v[vfmin].begin(); it!=v[vfmin].end(); ++it)
       {
           vec=(*it).first;
           co=(*it).second;
           if((dist[vec]> co)&&(!viz[vec]))
           {
               dist[vec]=co;
               pred[vec]=vfmin;
               q.push({co, vec});
           }
       }
   }
}
void afis()
{
    int i;
    f2<<cost<<"\n"<<nrmuc<<"\n";
    for(i=1; i<=nrmuc; i++)
        f2<<muc[i].x<<' '<<muc[i].y<<"\n";
}
int main()
{
    citire();
    solutie();
    afis();
    return 0;
}