#include<bits/stdc++.h>

#define pb push_back

using namespace std;

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

const int maxn = 400100;

int gr[maxn],x[maxn],y[maxn],c[maxn];

int n,m,rez,ind[maxn];

vector<int> v;

int grupa(int i)
{
	if (gr[i] == i) return i;
	gr[i] = grupa(gr[i]);
	return gr[i];
}

void reuniune(int i,int j)
{
	gr[grupa(i)] = grupa(j);
}

bool cmp(int i,int j)
{
	return(c[i] < c[j]);
}

int main()
{
    f>>n>>m;
	for(int i = 1;i <= m;++i)
	{
	    f>>x[i]>>y[i]>>c[i];
		ind[i] = i;
	}

	for(int i = 1;i <= n; ++i) gr[i] = i;

	sort(ind + 1,ind + m + 1,cmp);

	for(int i = 1;i <= m; ++i)
	{
		if (grupa(x[ind[i]]) != grupa(y[ind[i]])){
			rez += c[ind[i]];
			reuniune(x[ind[i]],y[ind[i]]);
			v.pb(ind[i]);
		}
	}
	g<<rez<<'\n'<<n-1<<'\n';

	for(int i = 0;i < n - 1; ++i)
        g<<x[v[i]]<<' '<<y[v[i]]<<'\n';

	return 0;
}