#include <bits/stdc++.h>
#define N 200100
#define M 400100

using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
vector<ii> apm;
int c[N];
iii e[M];
priority_queue<iii> Q;
int n,m,a,b,d;

int Find(int x){return (x==c[x])?x:Find(c[x]);}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<m;++i)
	{
		cin>>e[i].second.first>>e[i].second.second>>e[i].first;
	}
	for(int i=1;i<=n;++i)
		c[i]=i;
	sort(e,e+m);
	long long sum=0;
	for(int i=0;i<m;++i)
	{
		int d=e[i].first;
		int a=e[i].second.first;
		int b=e[i].second.second;
		int t1=Find(a);
		int t2=Find(b);
		if(t1!=t2)
		{
			c[t2]=t1;
			c[a]=t1;
			c[b]=t1;
			sum+=d;
			apm.push_back(ii(b,a));
		}
	}
	cout<<sum<<"\n";
	cout<<apm.size()<<"\n";
	for(int i=0;i<apm.size();++i)
		cout<<apm[i].first<<" "<<apm[i].second<<"\n";
	return 0;
}