#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#define f first
#define s second
using namespace std;

const int maxn = 200005;

struct edge { 
	int x , y , cost;
};

struct muchie {
	int x , y;
};

bool in[maxn];
muchie sol[2 * maxn];
int n, m, a , b , c, i , j; 
vector <int> G[maxn];
vector <int> C[maxn];


struct cmp  {  bool operator() (const muchie &a, const muchie &b)  {  return (C[a.x][a.y] > C[b.x][b.y] ); }  };

priority_queue < muchie , vector < muchie > , cmp > Q;

void Prim()
{
	int L = 1 , size = 1 , i , rez = 0 , k = 0;
	in[L] = 1;
	
	while (size < n ) {
		for (i = 0 ; i < G[L].size() ; ++i)
			if ( in[G[L][i]] == false ) {
				muchie E; E.x = L , E.y = i;
				Q.push(E);
			}
		while ( in[Q.top().x] && in[G[Q.top().x][Q.top().y]]) Q.pop();
		muchie act = Q.top();Q.pop();
		sol[++k].x = act.x , sol[k].y = G[act.x][act.y];
		rez += C[act.x][act.y];
		L = G[act.x][act.y] , in[L] = 1;
		size++;
		
	}
		printf("%d\n",rez);
		printf("%d\n",n - 1);
		for( i = 1 ; i <= n - 1 ; ++i ) 
			printf("%d %d\n",sol[i].x,sol[i].y);
		
	
}
		

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",&a,&b,&c);
		G[a].push_back(b);
		G[b].push_back(a);
		C[a].push_back(c);
		C[b].push_back(c);
	}
	
	Prim();
	
return 0;
}