#include<vector>
#include<cstdio>
#define NMAX 200000
using namespace std;

int n,m,pos[NMAX+5];

struct EDGE  {   int v,v1,c;   };

vector <EDGE> graph[NMAX+5];
vector < pair <int, int> > res;
EDGE dmin[NMAX+5]; int sz;

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

void swap (int pos1, int pos2)
{
    EDGE aux1; int aux2;
    aux2=pos[dmin[pos1].v];  pos[dmin[pos1].v]=pos[dmin[pos2].v]; pos[dmin[pos2].v]=aux2;
    aux1=dmin[pos1]; dmin[pos1]=dmin[pos2]; dmin[pos2]=aux1;
}

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

void down (int poz)
{
    int minim;
    while(1)
        {
            minim=poz;
            if(poz*2 <=sz && dmin[poz*2].c < dmin[minim].c)
                minim=poz*2;
            if(poz*2+1 <=sz && dmin[poz*2+1].c < dmin[minim].c)
                minim=poz*2+1;
            if(minim==poz)
                return;
            swap(poz,minim);
        }
}

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

void scoate()
{
    pos[dmin[1].v]=-1;
    dmin[1]=dmin[sz];
    sz--;
    if(sz)
        pos[dmin[1].v]=1;
    down(1);
}

void update (int poz, int v, int val)
{
    dmin[poz].c=val;
    dmin[poz].v1=v;
    up(poz);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,x,y,c,pas=0,cost,v;
    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            graph[x].push_back(make(y,x,c));
            graph[y].push_back(make(x,y,c));
        }

    baga(1,0,0);
    cost=0;

    while(sz)
        {
            if(pas)
                res.push_back(make_pair(dmin[1].v,dmin[1].v1));
            pas=1;
            v=dmin[1].v;
            cost+=dmin[1].c;
            scoate();
            for(i=0;i<graph[v].size();i++)
                if(pos[graph[v][i].v]!=-1)
                    {
                        if(pos[graph[v][i].v]==0)
                            baga(graph[v][i].v,v,graph[v][i].c);
                        else
                            if(dmin[pos[graph[v][i].v]].c>graph[v][i].c)
                                update(pos[graph[v][i].v], v, graph[v][i].c);
                    }
        }
    printf("%d\n%d\n",cost,n-1);
    for(i=0;i<res.size();i++)
        printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}