#include <stdio.h>
#include <vector>
#include <set>
#define max 200010
const int inf=0x3f3f3f3f;
using namespace std;
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[max],*p;
int n,m,i,j,cost1,d[max],t[max],k,w;
char inq[max];
struct cmp{
    bool operator() (int i,int j) const
    { return d[i]<d[j]; }
};
void push(int i,int j,int c)
{
    lista *p=new lista;
    p->cost=c;
    p->nod=j;
    p->next=g[i];
    g[i]=p;
}
multiset <int,cmp> q;
multiset<int>::iterator it;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m>0; m--)
    {
        scanf("%d%d%d",&i,&j,&cost1);
        push(i,j,cost1); push(j,i,cost1);
    }
    cost1=0;
    memset(d,inf,sizeof(d));
    d[1]=0;
    q.insert(1); inq[1]=1;
    while(!q.empty())
    {
        k=*q.begin();  cost1+=d[k];
        q.erase(q.begin());
        for(p=g[k]; p!=NULL; p=p->next)
         if(d[p->nod]>p->cost)
         {
             w=p->nod;
             d[w]=p->cost;
             t[w]=k;
             if(!inq[w])
              {
                  inq[w]=1;
                  q.insert(w);
              }
         }
    }
    printf("%d\n%d\n",cost1,n-1);
    for(i=1; i<n; i++)
     if(t[i]) printf("%d %d\n",t[i],i);
    return 0;
}