#include<fstream>
#include<algorithm>
#include<vector>
#define f first
#define s second
#define mp make_pair
using namespace std;
const int NMAX=200005,MMAX=400005;
struct muchie{int x;int y;int c;};
int cmin,n,m,T[NMAX],RG[NMAX];
muchie a[MMAX];
vector< pair<int,int> >sol;
int comp(muchie a,muchie b)
{return a.c<b.c;}

int find(int x)
{int R,y;
 
	for(R=x;R!=T[R];R=T[R]);
	
	for(;x!=T[x];)
	{y=T[x];
	 T[x]=R;
	 x=y;
	}
 return R;
}

void unite(int x,int y)
{
 if(RG[x]>RG[y])
	T[y]=x;
   else
	   T[x]=y;
  if(RG[x]==RG[y])
		  RG[y]++;
}

int main()
{ifstream fin("apm.in");
 ofstream fout("apm.out");
  fin>>n>>m;
  int i,x;
	  
	  for(i=1;i<=m;++i)
	   fin>>a[i].x>>a[i].y>>a[i].c;
	  
  sort(a+1,a+m+1,comp);
   for(i=1;i<=n;++i)
	   {T[i]=i;RG[i]=1;}
   int nr=0;
   for(i=1;i<=m&&nr<n-1;++i)
     if(find(a[i].x)!=find(a[i].y))
		{unite(find(a[i].x),find(a[i].y));
	     ++nr;
		 cmin+=a[i].c;
		 sol.push_back(mp(a[i].x,a[i].y));
		}
  
  fout<<cmin<<'\n'<<sol.size()<<'\n';
   for(i=0;i<sol.size();++i)
	   fout<<sol[i].f<<" "<<sol[i].s<<'\n';
  
  fout.close();
  fin.close();
  return 0;
}