#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair< int , pair< int ,int > > punct;
vector<int> sol,P; vector<punct> v; punct muchie;
int n,m,i,cmax,nr,det(int); inline void read(),solve(),write();
int main()
	{read(); sort(v.begin(),v.end()); solve(); write(); return 0; }	
inline void read()
	{freopen("apm.in","rt",stdin); freopen("apm.out","wt",stdout); scanf("%d%d",&n,&m);
	 for(register int i=0;i<m;++i) scanf("%d%d%d",&muchie.y.x,&muchie.y.y,&muchie.x),v.push_back(muchie);
	 for(register int i=0;i<n;i++) P.push_back(i);
}
int det(int x)
	{int r=--x,y;
	 while(P[r]!=r) r=P[r];
	 while(x!=P[x]) {y=P[x]; P[x]=r; x=y; }
	 return r;
	}
inline void solve()
	{int conex1,conex2;
	 for(register int i=0;i<m && sol.size()<n-1;++i)
		{conex1=det(v[i].y.x); conex2=det(v[i].y.y);
		 if(conex1!=conex2) {cmax+=v[i].x; sol.push_back(i); P[conex1]=conex2; }
		}
	}
inline void write()
	{printf("%d\n%d\n",cmax,sol.size());
	 for(register int i=0;i<sol.size();++i) printf("%d %d\n",v[sol[i]].y.y,v[sol[i]].y.x);
	}