#include<fstream>
#include<vector>

#define dmax 200002
#define inf 32000

using namespace std;

vector<long> a[dmax];
vector<int> c[dmax];

int folosit[dmax],cmin[dmax];
long precedent[dmax];

long n,total;

void prim(long k, long l)
{
 long i;
 int min=inf,varfmin=0;
	
 for (i=0; i<a[k].size(); i++)
	 if (cmin[a[k][i]]>c[k][i])
		 cmin[a[k][i]]=c[k][i];
 
 folosit[k]=1; 
 precedent[k]=l;
 
 for (i=1; i<=n; i++)
	 if (folosit[i]==0 && min>cmin[i])
		 {
		  min=cmin[i];
		  varfmin=i;
		 }

 if (varfmin!=0)
	 {
	  total=total+min;
	  prim(varfmin,k);
	 }
}

int main()
{
 long m,i,x,y,z;
	
 ifstream fin("apm.in");
 fin>>n>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y>>z;
	  a[x].push_back(y);
	  c[x].push_back(z);
	  a[y].push_back(x);
	  c[y].push_back(z);
	 }
	
 for (i=1; i<=n; i++)
	 cmin[i]=inf;
 prim(1,0);
 
 ofstream fout("apm.out");
 
 fout<<total<<'\n';
 fout<<n-1<<'\n';
 for (i=1; i<=n; i++)
	 if (precedent[i]!=0)
		 fout<<i<<" "<<precedent[i]<<'\n';
 
 fin.close();
 fout.close();

 return 0;
}