#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
#define NMAX 200005
#define pii pair <int,int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
vector <pii> A[NMAX];
set < pair <int,pii> > H;
vector <pii> sol;
int n,m,rez;
char marc[NMAX];
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		A[x].pb(mp(y,z));
		A[y].pb(mp(x,z));
	}
	for (i=0; i<A[1].size(); i++)
	{
		x=A[1][i].f; y=A[1][i].s;
		H.insert(mp(y,mp(x,1)));
	}
	marc[1]=1;
	for (i=2; i<=n; i++)
	{
		while (marc[(*H.begin()).s.f])
			H.erase(H.begin());
		x=(*H.begin()).s.f; y=(*H.begin()).f;
		sol.pb((*H.begin()).s);
		H.erase(H.begin());
		rez+=y;
		marc[x]=1;
		for (j=0; j<A[x].size(); j++)
		{
			y=A[x][j].f; z=A[x][j].s;
			if (!marc[y])
				H.insert(mp(z,mp(y,x)));
		}
	}
	printf("%d\n",rez);
	printf("%d\n",sol.size());
	for (i=0; i<sol.size(); i++)
		printf("%d %d\n",sol[i].f,sol[i].s);
	return 0;
}