#include <stdio.h>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
int i,j,k,l,n,m,s,nrsol,spart;
int x[20001],y[20001],c[20001];
int ind[20001],g[20001];
int vc[20001];
vector<int> v;
int Multime(int x)
{
     if (g[x]==x)
        return x;
     g[x]=Multime(g[x]);
     return g[x];
}
void unite (int a,int b)
{
     g[Multime(a)]=Multime(b);
}
bool cmp(int x,int y)
{
    return (c[x]<c[y]);
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf ("%d %d",&n,&m);
    for (i=1;i<=m;++i){
        scanf ("%d %d %d\n",&x[i],&y[i],&c[i]);
        ind[i]=i;
        }
    for (i=1;i<=n;++i)g[i]=i;
    sort(ind+1,ind+m+1,cmp);
    for (i=1;i<=m;++i){
        if (Multime(x[ind[i]])!=Multime(y[ind[i]])){
           s+=c[ind[i]];
           unite(x[ind[i]],y[ind[i]]);
           v.pb(ind[i]);
           }
        }
    printf ("%d\n",s);
    printf ("%d\n",n-1);
    for (i=0;i<n-1;++i)
        printf("%d %d\n",x[v[i]],y[v[i]]);
        
    return 0;
}