#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=200001;
using namespace std;

int n,m,chk[maxn];

vector<vector<pair<int,int>>> A(maxn,vector<pair<int,int>>());

struct mata{
	ll cost;
	ll curr;
	ll prev;
	
	bool operator< (const mata &A) const {
		return cost<A.cost;
	}
	
};

multiset<mata> Set;
vector<pair<int,int>> ans;

int main(){
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int c1,c2,c3;
		cin>>c1>>c2>>c3;
		A[c1-1].push_back({c2-1,c3});
		A[c2-1].push_back({c1-1,c3});
	}
	ll ansl=0;
	Set.insert({0,0,0});
	while(Set.size()){
		int i=Set.begin()->curr;
		int cost=Set.begin()->cost;
		int prev=Set.begin()->prev;
		Set.erase(Set.begin());
		if(chk[i])continue;
		chk[i]=1;
		ans.push_back({i,prev});
		ansl+=cost;
		for(int j=0;j<A[i].size();j++){
			if(!chk[A[i][j].F]){
				Set.insert({A[i][j].S,A[i][j].F,i});
			}
		}
	}
	cout<<ansl<<endl;
	cout<<ans.size()-1<<endl;
	for(int i=1;i<ans.size();i++){
		cout<<ans[i].F+1<<" "<<ans[i].S+1<<endl;
	}
}