#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;
 

#ifndef TEST
ifstream fin ("apm.in");
ofstream fout ("apm.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
 
#define MAXN 200000
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pp;

int n,m;
int a[MAXN];

struct edge
{
	int f,t,c;
};

edge e[MAXN*2];

vector<edge> rez;

int get_parent(int x)
{
	if (a[x] == x) return x;
	a[x] = get_parent ( a[x]);
	return a[x];
}

bool comp(edge x, edge y)
{
	return (x.c<y.c);
}

int main()
{
	fin>>n>>m;

	for (int i=0; i<m; i++)
	{
		fin>>e[i].f>>e[i].t>>e[i].c;
		e[i].f--;
		e[i].t--;
	}

	for (int i=0; i<n; i++)
		a[i]=i;

	sort(e,e+m,comp);

	int it=0;
	int cost = 0;

	for (int i=0; i<n-1; i++)
	{
		check:
		if (get_parent(e[it].f) != get_parent(e[it].t)) 
		{
			rez.pb(e[it]);
			a[a[ e[it].f ]] = a[ e[it].t];
			cost+=e[it].c;
		} else 
		{
			it++;
			goto check;
		}
	}

	fout<<cost;
	fout<<'\n';
	fout<<n-1;
	fout<<'\n';
	for (int i=0; i<n-1; i++)
		fout<<rez[i].f+1<<' '<<rez[i].t+1<<'\n';

    return 0;
}