#include<stdio.h>
#include<vector>
using namespace std;
#define NMAX 200000

int n,sz,pos[NMAX+10],sol[NMAX+10];

struct EDGE  { int v, c; };
vector <EDGE> graph[NMAX+10];
EDGE dmin[NMAX+10];
vector < pair <int, int> > res;

EDGE make (int a, int b)
{
    EDGE res={a,b};
    return res;
}

void swap (EDGE &a, EDGE &b)
{
    int ax=pos[a.v];
    pos[a.v]=pos[b.v];
    pos[b.v]=ax;
    EDGE aux=a;
    a=b;
    b=aux;

}

void up (int pos)
{
    while(pos>1 && dmin[pos>>1].c>dmin[pos].c)
        {
            swap(dmin[pos>>1],dmin[pos]);
            pos>>=1;
        }
}

void baga (int nod, int c)
{
    dmin[++sz]=make(nod,c);
    pos[nod]=sz;
    up(sz);
}

void scoate ()
{
    int poz,mic,nod;
    nod=dmin[1].v;
    swap(dmin[1],dmin[sz]);
    sz--;
    poz=1;
    while(1)
        {
            mic=poz;
            if(poz*2<=sz && dmin[poz*2].c < dmin[mic].c)
                mic=poz*2;
            if(poz*2+1<=sz && dmin[poz*2+1].c < dmin[mic].c)
                mic=poz*2+1;

            if(poz==mic)
                break;

            swap(dmin[poz],dmin[mic]);
            poz=mic;
        }
    pos[nod]=-1;
}

void update (int nod, int val)
{
    dmin[pos[nod]].c=val;
    up(pos[nod]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int m,i,x,y,ans=0,nod,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            graph[x].push_back(make(y,c));
            graph[y].push_back(make(x,c));
        }

    baga(1,0);
    while(sz)
        {
            nod=dmin[1].v;
            if(nod!=1)
                res.push_back(make_pair(nod,sol[nod]));
            ans+=dmin[1].c;
            scoate();
            for(i=0;i<graph[nod].size();i++)
                if(pos[graph[nod][i].v]!=-1)
                    {
                        if(pos[graph[nod][i].v]==0)
                            {
                                baga(graph[nod][i].v, graph[nod][i].c);
                                sol[graph[nod][i].v]=nod;
                            }
                        else
                            if(dmin[pos[graph[nod][i].v]].c > graph[nod][i].c)
                                {
                                    update(graph[nod][i].v, graph[nod][i].c);
                                    sol[graph[nod][i].v]=nod;
                                }
                    }
        }

    printf("%d\n%d\n",ans,n-1);
    for(i=0;i<res.size();i++)
        printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}