#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define maxn 200010
#define maxm 400010

vector < pair <int, int> > a[maxn],sol;
int pos[maxn],viz[maxn],n,m,c,size;
typedef struct muchie{
	int nod,arb,cost;};
muchie h[maxn];

void sw(int x, int y){
	swap(h[x],h[y]);
	pos[h[x].nod]=x;
	pos[h[y].nod]=y;}

void read(){
	ifstream f("apm.in");
	f>>n>>m;
	int x,y,c;
	for(int i=1;i<=m;i++){
		f>>x>>y>>c;
		a[x].push_back(make_pair(y,c));
		a[y].push_back(make_pair(x,c));}
	f.close();}

void push(int k){
	while(k/2&&h[k/2].cost>h[k].cost){
		sw(k,k/2);
		k=k/2;}}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=size){
			son=k*2;
			if(k*2+1<=size&&h[k*2+1].cost<h[k*2].cost)
				son=k*2+1;
			if(h[son].cost>h[k].cost)
				son=0;}
		if(son){
			sw(son,k);
			k=son;}}
	while(son);}

void pop(){
	pos[h[1].nod]=0;
	sw(1,size);
	size--;
	sift(1);}

void updateheap(int k){
	if(k/2&&h[k/2].cost>h[k].cost)
		push(k);
	else sift(k);}

void update (int nod){
	viz[nod]=1;
	int sz=a[nod].size()-1;
	for(int i=sz;i>=0;i--)
		if(!viz[a[nod][i].first])
			if(!pos[a[nod][i].first]){
				size++;
				h[size].nod=a[nod][i].first;
				pos[h[size].nod]=size;
				h[size].arb=nod;
				h[size].cost=a[nod][i].second;
				push(size);}
			else 
				if(h[pos[a[nod][i].first]].cost>a[nod][i].second){
					h[pos[a[nod][i].first]].arb=nod;
					h[pos[a[nod][i].first]].cost=a[nod][i].second;
					updateheap(pos[a[nod][i].first]);}}

void solve(){
	viz[1]=1;
	int sz,i,next;
	sz=a[1].size()-1;
	for(i=sz;i>=0;i--){
		size++;
		h[size].nod=a[1][i].first;
		pos[h[size].nod]=size;
		h[size].arb=1;
		h[size].cost=a[1][i].second;
		push(size);}
	for(i=1;i<n;i++){
		next=h[1].nod;
		c=c+h[1].cost;
		sol.push_back(make_pair(h[1].arb,h[1].nod));
		pop();
		update(next);}}

void write(){
	ofstream g("apm.out");
	g<<c<<"\n";
	int sz=sol.size();
	g<<sz<<"\n";
	for(int i=0;i<sz;i++)
		g<<sol[i].first<<" "<<sol[i].second<<"\n";
	g.close();}

int main(){
	read();
	solve();
	write();
	return 0;}