#include <fstream>
#include <vector>
using namespace std;
ifstream f("amp.in");
ofstream g("amp.out");
#define nmax 200000
long long minn,nr,cost;
bool viz[nmax];
long n,m,e1[nmax],e2[nmax];
vector<int> l[nmax],lc[nmax];
void read()
 {
 int i,x,y,c;
 f>>n>>m;
 for(i=1;i<=n;i++)
  {
  l[i].push_back(0);
  lc[i].push_back(0);
  }
 for(i=1;i<=m;i++)
  {
  f>>x>>y>>c;
  l[x][0]++;
  l[x].push_back(y);
  lc[x].push_back(c);
  if(c>0)
   minn+=c;
  l[y][0]++;
  l[y].push_back(x);
  lc[y].push_back(c);
  }
 }
bool mai_merge()
 {
 int i;
 for(i=1;i<=n;i++)
  if(!viz[i])
   return 1;
 return 0;
 }
void solve()
 {
 int i,k,ex1,ex2,mn,j;
 k=1;
 viz[k]=1;
 while(mai_merge())
  {
  mn=minn;
  for(i=1;i<=n;i++)
   {
   if(viz[i])
    {
    for(j=1;j<=l[i][0];j++)
     {
     if(lc[i][j]<mn&&!viz[l[i][j]])
      {
      mn=lc[i][j];
      ex1=i;
      ex2=l[i][j];
      }
     }
    }
   }
  viz[ex2]=1;
  e1[++nr]=ex1;
  e2[nr]=ex2;
  cost+=mn;
  }
 }
void show()
 {
 g<<cost<<endl<<nr<<endl;
 for(int i=1;i<=nr;i++)
  g<<e1[i]<<" "<<e2[i]<<endl;;
 }
int main()
 {
 read();
 solve();
 show();
  
 return 0;
 }