#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;


int g[400100],x[400100],y[400100],c[400100];
int n,m,a,in[400100];
vector<int> v;

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

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

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

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	cin>>n>>m;
	for(int i = 1;i <= m;i++)
	{
		cin>>x[i]>>y[i]>>c[i];
		in[i] = i;
	}

	for(int i = 1;i <= n; ++i)
        g[i] = i;
	sort(in + 1,in + m + 1,cmpf);
	for(int i = 1;i <= m; ++i)
	{
		if (grupa(x[in[i]]) != grupa(y[in[i]])){
			a += c[in[i]];
            reuniune(x[in[i]],y[in[i]]);
			v.push_back(in[i]);
		}
	}
	cout<<a<<endl;
	cout<<n-1<<endl;
	for(int i = 0;i < n - 1; i++)
		cout<<y[v[i]]<<" "<<x[v[i]]<<endl;
	return 0;
}