#include <cstdio>
#include <vector>
#include <algorithm>
#define MMAX 400005
#define NMAX 200005
using namespace std;

struct muchie
{
    int x,y,c;
}v[MMAX];
int n,m;
int mul[NMAX];
long long sum;
vector<muchie>sol;

muchie pp(int x,int y)
{
    muchie X;X.c=0;
    X.x=x;X.y=y;
    return X;
}

bool cmp(muchie p, muchie r)
{
    if (p.c > r.c) return 0;
        else return 1;
}

int tata(int nod)
{
    if (mul[nod] == nod) return nod;
    mul[nod]=tata(mul[nod]);
    return mul[nod];
}

void reuneste(int x, int y)
{
    mul[tata(x)] = tata(y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);

    for(int i = 1; i <= n; ++i) mul[i]=i;
    sort(v+1,v+m+1,cmp);

    for(int i = 1; i <= m; ++i)
    {
        if(tata(v[i].x) != tata(v[i].y))
        {
            reuneste(v[i].x,v[i].y);
            sum += v[i].c;
            sol.push_back(pp(v[i].x,v[i].y));
        }
    }

    printf("%lld\n%d\n",sum,n-1);
    for(int i = 0; i < sol.size(); ++i)
        printf("%d %d\n",sol[i].x,sol[i].y);
    return 0;
}