#include<bits/stdc++.h>
#define pb(x) push_back(x)
#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;
struct muc{long p,s,cs;}g[nmax];
long n,m,i,c[nmax/2],ans[nmax/2],j,ms=0,mx,mi,tot;
void qs(long left,long right) 
{
    long i=left,j=right;
    long pivot=g[(left+right)/2].cs;
    while(i<=j) 
	{
        while(g[i].cs<pivot)i++;
        while(g[j].cs>pivot)j--;
        if(i<=j) 
		{
            swap(g[i],g[j]);
            i++;
			j--;
        }
    }
    if(left<j)qs(left,j);
    if(i<right)qs(i,right);
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    cin>>n>>m;
    for(i=1;i<=n;i++)c[i]=i;
    for(i=1;i<=m;i++)cin>>g[i].p>>g[i].s>>g[i].cs;
    qs(1,m);
    for(i=1;ms<=n-2;i++)
	 if(c[g[i].p]!=c[g[i].s])
	 {
	 	ans[++ms]=i,mx=0,mi=inf,tot+=g[i].cs;
	 	mx=max(c[g[i].p],c[g[i].s]);
	 	mi=min(c[g[i].p],c[g[i].s]);
	 	for(j=1;j<=n;j++)if(c[j]==mx)c[j]=mi;
	 }
	cout<<tot<<endl<<ms<<endl;
	for(i=1;i<=ms;i++)cout<<g[ans[i]].p<<" "<<g[ans[i]].s<<endl;
	return 0;
}