#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=2e5+5;

int n,m,parent[NMAX],r1[NMAX],r2[NMAX];
vector <pair<int,pair<int,int> > >A;

int find(int a)
{
	if(parent[a]==a)
	    return a;
	return parent[a]=find(parent[a]);
}
void join(int a, int b)
{
    int x=find(a);
	int y=find(b);
	parent[y]=x;	
}

int main()
{
	
	fin >> n >> m;
	
	for(int i=1;i<=n;i++)
	    parent[i]=i;
	    
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		fin >> x >> y >> w;
		A.push_back(make_pair(w,make_pair(x,y)));
	}
	
	sort(A.begin(),A.end());
	
	int S=0,nr=0,k=0;
	while(nr<n-1)
	{
		int x=A[k].second.first;
		int y=A[k].second.second;
		int w=A[k].first;
		
		if(find(x)!=find(y))
		{
			join(x,y);
			S+=w;
			nr++;
			r1[nr]=x;
			r2[nr]=y;
		}
		k++;
	}
	
	fout << S << endl << n-1 << endl;
	for(int i=1;i<=nr;i++)
	    fout << r1[i] << " " << r2[i] << endl;
	
	return 0;
	
}