#include<cstdio>
#define INF 10000002
#define Nmx 200001

using namespace std;
int n,m,H[Nmx*4],viz[Nmx],nr,nrs,dist[Nmx];
struct nod
{
    int inf,cost;
    nod *urm;
};
nod *G[Nmx];
struct ssol
{
    int x,y;
}sol[Nmx];

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()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
        add(y,x,c);
    }
}

void schimb(int x,int y)
{
    int aux=H[x];
    H[x]=H[y];
    H[y]=aux;
}

void up_heap(int k)
{
    while(k>1)
    {
        if(dist[H[k/2]]<=dist[H[k]])
            return ;
        viz[H[k/2]]=k;
        viz[H[k]]=k/2;
        schimb(k,k/2);
        k=k/2;
    }
}

void downheap(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr&&dist[H[p+1]]<dist[H[p]])
            ++p;
        if(dist[H[p]]>dist[H[k]])
            return;
        viz[H[p]]=k;
        viz[H[k]]=p;
        schimb(p,k);
        k=p;
    }
}

void taie()
{
    viz[H[1]]=-1;
    schimb(1,nr);
    H[nr--]=0;
    if(nr>0)
    {
        viz[H[1]]=1;
        downheap(1);
    }
}


void solve()
{
    int ssol=0;
    for(int i=1;i<=n;++i)
        dist[i]=viz[i]=INF;
    dist[1]=0;
    viz[1] = 1;
    H[1]=1;
    nr = 1;
    for(int i=1;i<=n;++i)
    {
        int pzz=0,pk=0,mn=INF+1;
        pzz = H[1];
        taie();
        ssol+=dist[pzz];
        for(nod *p=G[pzz];p;p=p->urm)
        {
            if(viz[p->inf]==-1)
            {
                if(p->cost<mn)
                {
                    mn=p->cost;
                    pk=p->inf;
                }
                continue;
            }
            if(dist[p->inf]>p->cost)
            {
                dist[p->inf]=p->cost;
                if(viz[p->inf]==INF)
                {
                    H[++nr]=p->inf;
                    viz[p->inf]=nr;
                }
                up_heap(viz[p->inf]);
            }
        }
        if(i>1)
        {
            sol[++nrs].x=pzz;
            sol[nrs].y=pk;
        }
    }
    printf("%d\n",ssol);
    printf("%d\n",nrs);
    for(int i=1;i<=nrs;++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;
}