#include<cstdio>

using namespace std;

int n,m,viz[200001],nr;
int cost[200001],delacine[200001];

struct sl
{
    int x,y;
};
sl sol[200001];

struct nod
{
    int inf,cost;
    nod *urm;
};
nod *G[200001];

void add(int x,int y,int c)
{
    nod *aux= new nod;
    aux->inf = y;
    aux->cost = c;
    aux->urm = G[x];
    G[x]=aux;
}

void citire()
{
    scanf("%d%d",&n,&m);
    int x,c,y;
    for(int i=1 ;i <= m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        add(y,x,c);
    }
}

void solve()
{
    for(int i = 2;i<=n;++i)
    {
        int mnm = 100000001;
        for(nod *p = G[i] ; p ; p = p->urm)
            if(p->cost < mnm && p->inf==1)
            mnm = p->cost;
        cost[i]=mnm;
        delacine[i]=1;
    }
    int cstapm = 0;
    viz[1]=1;
    for(int i = 2;i<=n;++i)
    {
        int mnm = 1000001, pz;
        for(int k=1;k <= n;++k)
            if(viz[k]==0 && cost[k]<mnm)
            {
                mnm = cost[k];
                pz = k;
            }
        viz[pz] = 1;
        cstapm += mnm;
        sol[++nr].x = pz;
        sol[nr].y = delacine[pz];
        for(nod *p = G[pz]; p ; p=p->urm)
            if(p->cost < cost[p->inf])
            {
                cost[p->inf]=p->cost;
                delacine[p->inf]=pz;
            }
    }
    printf("%d\n%d\n",cstapm,n-1);
    for(int i=1;i<=nr;++i)
        printf("%d %d\n",sol[i].x,sol[i].y);
}

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