#include <cstdio>
#include <algorithm>
#define Nmx 400001

using namespace std;

int n,m,tata[Nmx];
struct much
{
    int x,y,cost;
    bool viz;
};
much G[Nmx];

struct cmp
{
    bool operator()(const much &a,const much &b)
    {
        return a.cost<b.cost;
    }
};

void citire()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        tata[i]=i;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].cost);
        G[i].viz=0;
    }
}

int rad(int k)
{
    int Q=k;
    while(tata[Q]!=Q)
        Q = tata[Q];
    while(tata[k]!=k)
    {
        k=tata[k];
        tata[k]=Q;
    }
    return Q;
}

void solve()
{
    sort(G+1,G+1+m,cmp());
    int sol=0;
    for(int i=1;i<=m;++i)
    {

        if(rad(G[i].x)!=rad(G[i].y))
        {
            tata[rad(G[i].x)]=tata[rad(G[i].y)];
            sol+=G[i].cost;
            G[i].viz  = true;
        }
    }
    printf("%d\n%d\n",sol,n-1);
    for(int i=1;i<=m;++i)
        if(G[i].viz==true)
            printf("%d %d\n",G[i].x,G[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    solve();
    return 0;
}