#include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
using namespace std;

vector < pair <int, pair <int, int> > > v;
struct {int xx,yy;} b[200010];
int i,n,sum,nr,k,t[200010],m,x,y,z,c;

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,&z);
        v.push_back(make_pair(z,make_pair(x,y)));
    }
    sort(v.begin(),v.end());
    for (i=1; i<=n; i++)
         t[i]=i;
    for (i=0; i<v.size(); i++)
    {
        c=v[i].first;
        x=v[i].second.first;
        y=v[i].second.second;
        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;
}