#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define forn(i,a,b) for (int i = a; i <= b; i++)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
#define er erase
#define in insert
#define pi pair <int, int>
#define pii pair <pi, pi>
# define sz(x) (int)((x).size())
#define inf 1000000000
const ll mod = 1000000007;
int parent[200005],size[200005],n,m,k,x,y,z,sum;
vector<pair<int,pi>>v;
vector<pi>ans;
ifstream in("amp.in");
ofstream out("amp.out");
int find_set(int x){
	if(x==parent[x])return x;
	return parent[x]=find_set(parent[x]);
}
void unionn(int x,int y){
	x=find_set(x);
	y=find_set(y);
	if(x!=y){
		if(size[x]<size[y])swap(x,y);
		parent[y]=x;
		size[x]+=size[y];
	}
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(); cerr.tie(); cout.tie();
	in>>n>>m;
	while(m--){
		in>>x>>y>>z;
		v.pb(mp(z,mp(x,y)));
	}
	sort(all(v));
	forn(i,1,n)parent[i]=i,size[i]=1;

	for(auto it:v){
		if(find_set(it.ss.ff)!=find_set(it.ss.ss)){
			unionn(it.ss.ff,it.ss.ss);
			ans.pb(mp(it.ss.ff,it.ss.ss));
			sum+=it.ff;
		}
	}
	out<<sum<<'\n'<<sz(ans)<<'\n';
	for(auto it :ans){
		out<<it.ff<<' '<<it.ss<<'\n';
	}
return 0;
}