#include <cstdio>
#include <vector>
#include <queue>
#define INF 2000000000
#define NMAX 200002

using namespace std;
int n, r=1;
vector < pair<int,int> > G[NMAX];
int cmin[NMAX];
int p[NMAX];
bool Z[NMAX];

class ComparVf
{public:
 bool operator () (const int& x, const int& y)
 { return cmin[x]>cmin[y]; }
};
priority_queue<int, vector<int>, ComparVf> H;

void Citire();
void Prim();
void Afisare();

int main()
{
 Citire();
 Prim();
 Afisare();
 return 0;
}

void Citire()
{int i, m, x, y, c;
 FILE * fin=fopen("apm.in","r");
 fscanf(fin,"%d %d", &n, &m);
 for (i=0; i<m; i++)
     { fscanf(fin,"%d %d %d", &x, &y, &c);
       G[x].push_back(make_pair(y,c));
       G[y].push_back(make_pair(x,c));
    }
}

void Prim()
{int i, vfmin;
 for (i=1; i<=n; i++) {cmin[i]=INF; p[i]=r;}
 cmin[r]=0; p[r]=0;
 H.push(r); Z[r]=1;
 while (!H.empty())
	   {vfmin=H.top(); H.pop();
	    Z[vfmin]=1;
	    for (i=0; i<G[vfmin].size(); i++)
	       //parcurg lista de adiacenta a lui vfmin
           if (!Z[G[vfmin][i].first])
              if (cmin[G[vfmin][i].first] > G[vfmin][i].second)//optimizez
		         { cmin[G[vfmin][i].first] = G[vfmin][i].second;
			       p[G[vfmin][i].first]=vfmin;
		           H.push(G[vfmin][i].first);
		         }
       }
 }

void Afisare()
{ int i;
  long long int cost=0;
  FILE * fout=fopen("apm.out","w");
  for (i=1; i<=n; i++) cost += cmin[i];
  fprintf(fout,"%lld\n%d\n",cost,n-1);
  for (i=1; i<=n; i++)
       if (i!=r)
          fprintf(fout,"%d %d\n", i, p[i]);
  fclose(fout);
}