#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

int t[200002];
vector<int> v[200002];
bool viz[200002];
int n,m;
int nrmuc;
int x,y,cost;

int sef(int x)
{
	if(x != t[x])
		t[x] = sef(t[x]);
	return t[x];
}

void join(int x,int y)
{
	int t1 = sef(x);
	int t2 = sef(y);
	t[t2]=t1;
}

struct apm
{
	int n1,n2,c;
};

apm cit[400001];

bool cmp(apm a,apm b)
{
	if(a.c < b.c)
		return 1;
	return 0;
}

int main()
{
    in>>n>>m;
    for(int i = 1; i<=n; i++)
		{
           t[i]=i;
		}
    for(int i = 1; i<=m; i++)
		{
			in>>x>>y>>cost;
			cit[i].n1 = x;
			cit[i].n2 = y;
			cit[i].c = cost;
		}
		sort(cit + 1,cit + m + 1,cmp);
		int i = 1;
		cost = 0;
		while(nrmuc != n - 1)
		{
			int n1, n2; n1 = cit[i].n1; n2 = cit[i].n2;
			if(sef(n1) != sef(n2))
			{
			    ++nrmuc;
				join(n1,n2);
				v[n1].push_back(n2);
				v[n2].push_back(n1);
				cost += cit[i].c;
			}
			++i;
		}
		out<<cost<<"\n"<<n - 1<<"\n";
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j<v[i].size();j++)
				if(i<v[i][j])
					out<<i<<" "<<v[i][j]<<"\n";

		}
    return 0;

}