#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define nmax 400001
const int inf=INT_MAX;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
int n,m,c,x,y,i,j,nr=1,tot,viz[nmax],key[nmax],par[nmax],mi,in;
vector<pair<int,int> >a[nmax];
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	freopen("amp.in","r",stdin);
	freopen("apm.out","w",stdout);
    cin>>n>>m;
    for(i=1;i<=m;i++)
	{
		cin>>x>>y>>c;
		a[x].push_back({y,c});
		a[y].push_back({x,c});
	}
	for(i=1;i<=n;i++)key[i]=inf;
	key[1]=0,par[1]=-1;
	for(i=1;i<=n;i++)
	{
		mi=inf;
		for(j=1;j<=n;j++)if(!viz[j] && key[j]<mi)mi=key[j],in=j;
		tot+=mi;
		viz[in]=1;
		for(j=0;j<a[in].size();j++)
		 if(!viz[a[in][j].first] && a[in][j].second<key[a[in][j].first])
		  par[a[in][j].first]=in,key[a[in][j].first]=a[in][j].second;
	}
	cout<<tot<<endl<<n-1<<endl;
	for(i=2;i<=n;i++)cout<<par[i]<<" "<<i<<endl;
	return 0;
}