#include <cstdio>
#include <vector>
#include <algorithm>
#define lim 400100
using namespace std;

int x[lim];
int y[lim];
int c[lim];
int ind[lim];
int gr[lim/2];
vector <int> G;
int n,m;
void citire()
{
    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;
        }
}


int grupa(int x)
{
    if(gr[x] == x)
    return x;
    gr[x] = grupa(gr[x]);
    return gr[x];
}


void reunim(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}

struct cmp
{
    bool operator () (const int &a, const int &b)const
        {
            return c[a]<c[b];
        }
};
int cost = 0;
void kruskal()
{
    sort(ind+1,ind+1+m,cmp());
        for(int i=1;i<=n;i++)
            gr[i] = i;

        for(int i=1;i<=m;i++)
        {
            if( grupa(x[ind[i]]) != grupa(y[ind[i]]) )
            {
                reunim(x[ind[i]],y[ind[i]]);
                cost+= c[ind[i]];
                G.push_back(ind[i]);
            }
        }

}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    printf("%d\n%d\n",cost,G.size());
    for(int i=0;i<G.size();i++)
        {
            printf("%d %d\n",x[G[i]],y[G[i]]);
        }
    return 0;
}