#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

FILE *in,*out;

int n,m;

struct Muchii
{
    int a,b,cost;
};

/*bool operator < (const Muchii &x,const Muchii &y)
{
    return x.cost < y.cost;
}*/

Muchii v[400005];

int tata[200005];

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

int rez[200005];
int maxlen[200005];


void unionfind(int x,int y)
{
    if(maxlen[x] > maxlen[y])
        tata[y] = x;
    else if(maxlen[y] > maxlen[x])
        tata[x] = y;
    else{
        tata[x] = y;
        maxlen[y] ++;
    }
}

int cmp(Muchii a,Muchii b)
{
    return a.cost < b.cost;
}

vector <Muchii> sol;

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].a,&v[i].b,&v[i].cost);
    }
    sort(v+1,v+m+1,cmp);
    for(int i = 1;i <= n;i ++)
        maxlen[i] = 1;
    int sum = 0,nrsol = 0;
    for(int i = 1;i <= m;i ++)
    {
        if(dad(v[i].a) != dad(v[i].b))
        {
            rez[++rez[0]] = i;
            sum += v[i].cost;
            unionfind(dad(v[i].a),dad(v[i].b));
            sol.push_back(v[i]);
            nrsol ++;
        }

    }
    printf("%d\n%d\n",sum,n-1);
    for(int i = 0;i < nrsol;i ++)
    {
        printf("%d %d\n",sol[i].a,sol[i].b);
    }


    return 0;
}