#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "apm.in"
#define FOUT "apm.out"
#define NMAX 200002
#define MMAX 400002
using namespace std;


struct G
{
	int e;
	int cost;
	int poz;
	G* next;
};
typedef G* g;
g gr[NMAX];
int aux,t,cost_t,cost[MMAX],m,n,h[NMAX],viz[NMAX],poz_heap[NMAX],k,x,y,c,fiu;
pair<int,int> muchii[MMAX];
vector< pair<int,int> > apm;

void push(g &act,int x,int c,int poz)
{
	g ax=new G;
	ax->e=x;
	ax->cost=c;
	ax->poz=poz;
	ax->next=act;
	act=ax;
}

void swap(int x,int y)
{
     aux = h[x];
     h[x] = h[y];
     h[y] = aux;
}

void upheap(int poz)
{
	while(poz>1)
	{
		t = poz>>1;
		if(cost[h[t]] > cost[h[poz]]) 
		{
			poz_heap[h[t]] = poz;
            poz_heap[h[poz]] = t;
            swap(poz,t);
            poz=t;
		}
		else poz=1;                                  
	}   
}

void downheap(int poz)
{
	while(poz <= k)
	{
		fiu = poz<<1;
		if(fiu <= k)
		{
			if(fiu+1<=k && cost[h[fiu]] > cost[h[fiu + 1]])
				fiu++;
		}
		else return; 
		if(cost[h[poz]]>cost[h[fiu]]) 
		{
			poz_heap[h[fiu]] = poz;
            poz_heap[h[poz]] = fiu;
            swap(poz,fiu);
            poz = fiu;;
		} 
		else poz = k+1;
	}
}     

void prim()
{
  int gasit,val,nod,contor=1;
  viz[1] = 1;
  for(g i=gr[1];i;i=i->next)
	  {
		  k++;
		  h[k] = i->poz;
          upheap(k);
	  }
	  while(contor <= n-1)
	  {
		  gasit=0;
		  while(!gasit && k)
		  {
			  val = h[1];
			  swap(1,k);
			  k--;
			  downheap(1);
			  if(!viz[muchii[val].first] || ! viz[muchii[val].second]) gasit=1;
		  }
		  cost_t += cost[val];
		  apm.push_back(muchii[val]);
		  contor++;
		  if(viz[muchii[val].first]==0) 
		  {
			  viz[muchii[val].first]=1;
              nod=muchii[val].first;
              for(g i=gr[nod];i;i=i->next) 
				  {
					  k++;
					  h[k]=i->poz;
					  upheap(k);
				  }
		  }     
		  if(viz[muchii[val].second]==0) 
		  {
			  viz[muchii[val].second]=1;
              nod=muchii[val].second;
              for(g i=gr[nod];i;i=i->next) 
				  {
					  k++;
                      h[k]=i->poz;
                      upheap(k);
				  }
		  }                                                                          
	  }   
}

int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		push(gr[x],y,c,i);
		push(gr[y],x,c,i);
        muchii[i]=make_pair(x,y);
        cost[i]=c; 
	}
	prim();    
	printf("%d\n%d\n",cost_t,n-1);
	vector<  pair<int,int> >::iterator it;
	for(it=apm.begin();it!=apm.end();it++)
	{
		printf("%d %d\n",it->first,it->second);
	}
    return 0;
}