#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m;
int d[200002],ph[200002],nrmc[200002],p[200002];
vector<int> mc[200002],cmc[200002];
class heap
{
public:
    int x[50005];
    int k;
    void insert(int a)
    {
        x[++k]=a;
		ph[a]=k;
        int aux,q=k;
        while(d[x[q/2]]>d[x[q]]&&q/2>=1)
        {
            aux=x[q/2];
            x[q/2]=x[q];
            x[q]=aux;
            ph[x[q]]=q/2;
            ph[x[q/2]]=q;
            q=q/2;
        }
    }
    void remove(int i)
    {
        x[i]=x[k--];
        int q=k,aux;
        while(1)
        {
            q=i;
            if(d[x[i]]>d[x[i*2]]&&i*2<=k)
                q=i*2;
            if(d[x[q]]>d[x[i*2+1]]&&i*2+1<=k)
                q++;
            aux=x[q],x[q]=x[i],x[i]=aux;
            ph[x[q]]=i; ph[x[i]]=q;
            if(q==i) break;
            i=q;
        }
    }
    void up(int i)
    {
        int aux;
        while(d[x[i/2]]>d[x[i]]&&i/2>=1)
        {
            aux=x[i/2];
            x[i/2]=x[i];
            x[i]=aux;
            ph[x[i/2]]=i;
            ph[x[i]]=i/2;
            i=i/2;
        }
    }
};heap h;
int nr;
long long S;
int main()
{
     freopen("apm.in","r",stdin);
     freopen("apm.out","w",stdout);
     int i,a,b,c;
     scanf("%d%d",&n,&m);
	 for(i=1;i<=n;i++)
		d[i]=200000000;
     for(i=1;i<=m;i++)
     {
          scanf("%d%d%d",&a,&b,&c);
          mc[a].push_back(b);
          cmc[a].push_back(c);
          mc[b].push_back(a);
          cmc[b].push_back(c);
          nrmc[a]++,nrmc[b]++;
     }
     h.k=0;
	 d[1]=0;
     int v,l;
     h.insert(1);
     while(h.k>0)
     {
          v=h.x[1];
          h.remove(1);
		  ph[v]=-1;
		  S=S+d[v],nr++;
          for(l=0;l<nrmc[v];l++)
          {
			  i=mc[v][l];
               if(ph[i]!=-1&&d[i]>cmc[v][l])
                {
					if(d[i]==200000000)
                    {
						d[i]=cmc[v][l];
                         h.insert(i);
                         p[i]=v;
                    }
                    else
                    {
                         d[i]=cmc[v][l];
                         p[i]=v;
                         h.up(ph[i]);
                    }
			   }
          }

     }
	printf("%lld\n%d\n",S,nr-1);
	for(i=2;i<=n;i++)
		if(d[i]!=200000000)
			printf("%d %d\n",p[i],i);

    return 0;
}