#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,t[200001];
struct {int xx; int yy;} b[200001];

int radx(int nod)
{
    if (t[nod]!=nod)
        t[nod]=radx(t[nod]);
    return t[nod];
}
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++)
         t[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;
        if (radx(x)!=radx(y))
        {
            sum+=c;
            b[++nr].xx=x; b[nr].yy=y;
            t[t[y]]=t[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;
}