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

int x[MMAX],y[MMAX],c[MMAX];
int n,m;
int mul[NMAX],ind[MMAX];
long long sum;
vector<int>sol;

bool cmp(int p, int r)
{
   return (c[p] < c[r]);
}

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",&x[i],&y[i],&c[i]);
            ind[i]=i;
        }

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

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

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