#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 200005
#define LMAX 400005
#define INF 1000000000
#define pii pair <int,int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
int n,m,rez,r,ant[NMAX],best[NMAX];
struct muchie{int a,b,c;};
muchie A[LMAX];
vector <int> B[NMAX];
priority_queue < pii > Q;
pii act,sol[NMAX];
bool viz[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&A[i].a,&A[i].b,&A[i].c);
		B[A[i].a].pb(i);
		B[A[i].b].pb(i);
	}
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void init()
{
	int i;
	for (i=2; i<=n; i++)
		best[i]=INF;
}
inline int find_diff(int edge,int nod)
{
	if (A[edge].a==nod)
		return A[edge].b;
	return A[edge].a;
}
void expand(int nod)
{
	int i,vec,cost,edge;
	for (i=0; i<B[nod].size(); i++)
	{
		edge=B[nod][i];
		vec=find_diff(edge,nod); cost=A[edge].c;
		if (best[vec]>cost)
		{
			best[vec]=cost; ant[vec]=nod;
			Q.push(mp(-cost,vec));
		}
	}
}
void solve()
{
	init();
	expand(1); viz[1]=1;
	while (!Q.empty())
	{
		act=Q.top();
		Q.pop();
		if (!viz[act.s])
		{
			sol[++r].f=act.s; sol[r].s=ant[act.s];
			rez+=(-act.f);
			viz[act.s]=1;
			expand(act.s);
		}
	}
	printf("%d\n%d\n",rez,n-1);
	int i;
	for (i=1; i<n; i++)
		printf("%d %d\n",sol[i].f,sol[i].s);
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	read();
	solve();
	return 0;
}