//algoritmul lui Kruskal

#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>

#define lmax1 200005
#define lmax2 400005
#define max 2002

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,nr,cost;

int grup[lmax1];

vector <pair<int,int> > v[max];

vector <int > comp[lmax1];

deque < pair<int,int> >sol;

inline void read()
{
    int x,y,z;

    f>>n>>m;

    for (int i=1;i<=m;i++)
     {
         f>>x>>y>>z;

         v[z+1000].push_back(make_pair(x,y));
     }

     for (int i=1;i<=n;i++)
      {
          grup[i]=i;
          comp[i].push_back(i);
      }

}

inline void solve()
{

    vector < pair <int,int> >::iterator it;

    for (int i=0;i<=2000;i++)
       for (it=v[i].begin();it<v[i].end();it++)
         if (grup[it->first]!=grup[it->second])
           {
               int x=grup[it->first]<grup[it->second]?grup[it->second]:grup[it->first];
               int mi=grup[it->first]>grup[it->second]?grup[it->second]:grup[it->first];

               for (int j=0;j<comp[x].size();j++)
                 {
                     comp[mi].push_back(comp[x][j]);
                     grup[comp[x][j]]=mi;
                 }

               nr++;
               cost+=i-1000;
               sol.push_back(make_pair(it->first,it->second));

              if (nr==n-1)
               {
                   i=2001;
                   break;
               }
           }
}

inline void write()
{
    vector <pair<int,int> >::iterator it;

    g<<cost<<'\n'<<n-1<<'\n';

    for (;sol.size();sol.pop_back())
      g<<sol.back().first<<" "<<sol.back().second<<'\n';
}

int main()
{

    read();

    solve();

    write();

    f.close();
    g.close();
}