#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;
#define NMAX 200200
#define INF 2000000200
int L,N,M,VEC[NMAX],ANS,V[NMAX],H[NMAX*2+100],POZ[NMAX],C[NMAX];
vector <pair<int,int> > VECT[NMAX],VANS;

void introducere_apm(int x)
{
	int nod,cost;
	for(unsigned int i=0;i<VECT[x].size();++i)
	{
		nod=VECT[x][i].first;
		cost=VECT[x][i].second;
		V[nod]=min(V[nod],cost);
		if(V[nod]==cost) VEC[nod]=x;
	}

}

void push(int poz)
{
while((poz*2<=L&&V[H[poz]]>V[H[poz*2]])|| (poz*2+1<=L&&V[H[poz*2+1]]<V[H[poz]]))
if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)         
        {
            swap(H[poz],H[poz * 2]);
            swap(POZ[H[poz]],POZ[H[poz * 2]]);
            poz=poz*2;
        }
        else
        {

        	swap(H[poz],H[poz*2+1]);
        	swap(POZ[H[poz]],POZ[H[poz*2+1]]);
        	poz=poz*2+1;
        }


}

void pop(int poz)
{	
while(poz>1 && V[H[poz]]<V[H[poz/2]])
{

	swap(H[poz],H[poz/2]);
	swap(POZ[H[poz]],POZ[H[poz/2]]);
	poz/=2;
}

}
void introduce_heap(int nod)
{
	H[++L]=nod;
	POZ[nod]=L;
	pop(L);

}

int scoate_heap()
{
	int x=H[1];
	swap(H[1],H[L]);
	swap(POZ[H[1]],POZ[H[L]]);
	L--;
	push(1);
	POZ[x]=0;

return x;

}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
VECT[x].push_back(make_pair(y,c));
VECT[y].push_back(make_pair(x,c));
}

for(int i=1;i<=N;++i)
	V[i]=INF;
V[1]=0;
introducere_apm(1);
for(int i=2;i<=N;++i)
{
	introduce_heap(i);
}
for(int i=2;i<=N;++i)
{
	int x=scoate_heap();
	introducere_apm(x);
	ANS+=V[x];
	VANS.push_back(make_pair(x,VEC[x]));
	for(unsigned int j=0;j<VECT[x].size();++j)
	{
		int nod=VECT[x][j].first;
		if(POZ[nod]) pop(POZ[nod]);

	}
}

printf("%d\n",ANS);
printf("%d\n",N-1);
for(int i=0;i<N-1;++i)
printf("%d %d\n",VANS[i].first,VANS[i].second);
	return 0;
}