#include <stdio.h>
# include <algorithm>
# include <vector>
using namespace std;
vector <pair <int, pair<int, int> > > l;
vector <pair <int, pair<int, int> > > :: iterator it;
int n,m,x,y,c,i,j,nr,sum,a[200001];
struct {int xx; int yy;} b[200001];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        l.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(l.begin(),l.end());
    for (i=1; i<=n; i++)
         a[i]=i;
    sum=0;
    for (i=0; i<l.size() && nr<n-1; ++i)
    {
        x=l[i].second.first;
        y=l[i].second.second;
        c=l[i].first;
        int q=a[y];
        if (a[x]!=a[y])
        {
            sum+=c; b[++nr].xx=x; b[nr].yy=y;
            for (j=1; j<=n; j++)
            if (a[j]==q) a[j]=a[x];
        }
    }
    printf("%d\n",sum);
    printf("%d\n",nr);
    for (i=1; i<=nr; i++)
       printf("%d %d\n",b[i].xx,b[i].yy);
    return 0;
}