#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMax=200005;
const int oo=(1 << 30);

int N,M;
int S,nr,rasp[NMax];
bool visit[NMax];
int Cost[NMax];

vector <pair <int,int> >a[NMax];

struct comp
{
	bool operator()(int a, int b)
	{
		return Cost[a]>Cost[b];
	}
};

priority_queue <int, vector<int>, comp> coada;

void Citeste()
{
	fin >> N >> M;
	for(int i=1;i<=M;i++)
	{
		int x,y,c;
		fin >> x >> y >> c;
		a[x].push_back(make_pair(y,c));
		a[y].push_back(make_pair(x,c));
	}
	for(int i=1;i<=N;i++)
	    Cost[i]=oo;
}
void Prim(int st)
{
	visit[st]=true;
	coada.push(st);
	Cost[st]=0;
	while(!coada.empty())
	{
		int Nod=coada.top();
		coada.pop();
		visit[Nod]=true;
		nr++;
		rasp[nr]=Nod;
		S+=Cost[Nod];
		for(int i=0;i<a[Nod].size();i++)
		{
			int Vecin=a[Nod][i].first;
			int C=a[Nod][i].second;
			if(C<Cost[Vecin])
			    Cost[Vecin]=C;
			if(visit[Vecin]==false)
			{
				coada.push(Vecin);
				visit[Vecin]=true;
			}
		}
	}
}
int main()
{
	
	Citeste();
	Prim(1);
	
	fout << S << endl << N-1 << endl;
	
	for(int i=1;i<nr;i++)
	    fout << rasp[i] << " " << rasp[i+1] << endl;
	
	return 0;
	
}