#include<stdio.h>
#include<cstring>
using namespace std;
FILE *f,*g;
int n,m,l;
char viz[200002];
int d[200002],list[200002];

struct nod 
{
	int v,c;
	nod *adresa;
};
nod *a[200002];

void adaug(int x,int y,int c)
{
	nod *p;
	p=new nod;
	p->v=x;
	p->c=c;
	p->adresa=a[y];
	a[y]=p;
}

void citire()
{
	int i,x,y,c;
	f=fopen("apm.in","rt");
	memset(a,0,sizeof(a));
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d",&x,&y,&c);
		adaug(x,y,c);
		adaug(y,x,c);
	}
	fclose(f);
}

void dijkstra()
{
	nod *p;
	int i,j,ok,nr,dmin;
	l=0;
	for(p=a[1];p;p=p->adresa)
	{
		l++;
		list[l]=p->v;
		d[l]=p->c;
	}
	viz[1]=1;
	nr=1;
	while(nr!=n)
	{
		dmin=100000000;
		for(i=1;i<=l;i++)
			if(viz[list[i]]==0 && d[i]<dmin)
			{
				dmin=d[i];
				j=i;
			}
		nr++;
		printf("%d %d\n",list[j],d[j]);
		viz[list[j]]=1;
		for(p=a[list[j]];p;p=p->adresa)
			if(viz[p->v]==0)
			{
				ok=0;
				for(i=1;i<=l;i++)
					if(p->v==list[i])
					{
						ok=1;
						if(d[i] > d[j]+p->c)
							d[i]=d[j]+p->c;
						break;
					}
				if(ok==0)
				{
					l++;
					list[l]=p->v;
					d[l]=d[j]+p->c;
				}
			}
	}
	
}

int main()
{
	citire();

	dijkstra();
	
	return 0;
}