#include <stdio.h>

#include <vector>

using namespace std;
int n,m,i,sum,t,x,y,pr,use[200004],nr,nr1;
struct nod {int t,n,pr;};
nod h[200004];
vector <int> v[200003],p[200004];
vector <nod> sol;

FILE *f,*g;
void dw (int k,int n)
{
    int st=k*2;
    if (st<=n)
    {
        if (h[st].pr>h[st+1].pr && st+1<=nr) st++;
        if (h[st].pr<h[k].pr)
        {
            swap (h[st],h[k]);
            dw (st,n);
        }
    }
}
void up (int k)
{
    t=k/2;
    if (t>=1 && h[t].pr>h[k].pr)
    {
        swap (h[t],h[k]);
        up (t);
    }
}
void scoate ()
{

    while (use[h[1].n]==1 && nr>=1)
    {
        swap (h[1],h[nr]);
        nr--;
        dw(1,nr);
    }

}
int main()
{
    f=fopen ("apm.in","r");
    g=fopen ("apm.out","w");
    fscanf (f,"%d%d",&n,&m);
    for (i=1;i<=n;i++)
        v[i].clear ();
    for (i=1;i<=m;i++)
    {
        fscanf (f,"%d%d%d",&x,&y,&pr);
        v[x].push_back (y);
        p[x].push_back (pr);
        v[y].push_back (x);
        p[y].push_back (pr);
    }
    int j;
    use[1]=1;

    nod ax,ay;
    for (j=0;j<v[1].size ();j++)
    {
        ax.t=1;
        ax.n=v[1][j];
        ax.pr=p[1][j];
        h[++nr]=ax;
        up(nr);
    }
   while (nr>=1)
   {
       ax=h[1];nr1++;
       sol.push_back (ax);
       use[ax.n]=1;

       sum+=ax.pr;
       scoate ();
       for (j=0;j<v[ax.n].size ();j++)
       {
           ay.t=ax.n;
           ay.pr=p[ax.n][j];
           ay.n=v[ax.n][j];
           if (use[ay.n]==0)
           {
              h[++nr]=ay;
              up (nr);
           }
       }
   }
fprintf (g,"%d\n%d\n",sum,nr1);
while (!sol.empty ())
{
    ax=sol.back ();
    sol.pop_back ();
    fprintf (g,"%d %d\n",ax.t,ax.n);
}
    return 0;
}