#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define maxN 200005
#define maxM 400005
#define pb push_back
#define mp make_pair
using namespace std;
vector < pair < int,pair < int,int > > > u;
vector < pair < int,int > > t;
int n,m,i,j,v[maxN],cost,x,y,c;
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		u.pb(mp(c,mp(x,y)));
	}
	sort(u.begin(),u.end());
	v[u[1].second.first]=1; v[u[1].second.second]=1; cost=u[1].first; t.pb(mp(u[1].second.first,u[1].second.second));
	for(i=1;i<n-1;++i)
	{
		j=0;
		while(v[u[j].second.first]==v[u[j].second.second]) j++;
		if(v[u[j].second.first]==1)
			v[u[j].second.second]=1;
		else
			v[u[j].second.first]=1;
		cost+=u[j].first;
		t.pb(mp(u[j].second.first,u[j].second.second));
	}
	printf("%d\n%d\n",cost,n-1);
	for(i=0;i<n-1;++i)
		printf("%d %d\n",t[i].first,t[i].second);
	return 0;
}