#include<fstream>
#define dmax 400010
#define dmax2 200010
using namespace std;

typedef struct muchie
{
 int x,y,c;
} muchie;

muchie mu[dmax];
int n,m;
long long cost;
int sol[dmax2][3];
int tata[dmax2],rang[dmax2];


void citire()
{
 int i;
	
 ifstream fin("apm.in");
 
 fin>>n>>m;
 for (i=1; i<=m; i++)
	  fin>>mu[i].x>>mu[i].y>>mu[i].c;
 
 fin.close();
}


bool comp(muchie a, muchie b)
{
 return a.c < b.c;
}


int find(int x)
{
 if (x != tata[x])
	 tata[x] = find(tata[x]);
 
 return tata[x];
}


void uneste(int x, int y)
{
 if (rang[x] > rang[y])
	 {
	  tata[y] = x;
	  rang[y]++;
	 } else
	 {
	  tata[x] = y;
	  rang[x]++;
	 }
}


void solve()
{
 int i,nrm=0;
	
 for (i=1; i<=n; i++)
	 tata[i] = i;
 
 for (i=1; i<=m; i++)
	 if (find(mu[i].x) != find(mu[i].y))
		 {
		  uneste(find(mu[i].x), find(mu[i].y));
		  nrm++; 
		  sol[nrm][1] = mu[i].x; sol[nrm][2] = mu[i].y; 
		  cost += mu[i].c;
		 }
}


void afisare()
{
 int i;
	
 ofstream fout("apm.out");
 
 fout<<cost<<'\n'<<n-1<<'\n';
 for (i=1; i<=n-1; i++)
	 fout<<sol[i][1]<<" "<<sol[i][2]<<'\n';
 
 fout.close();
}


int main()
{
	
 citire();
 sort(mu+1, mu+m+1, comp);
 solve();
 afisare();
	
 return 0;
}