#include<fstream>
#include<iostream>
using namespace std;
struct nod
{
	int vf;
	int val;
	nod *next;
};
#define nn 50005
#define inn 1<<10
nod *g[nn];
int n,m,d[nn];
void adauga(int a,int b,int c)
{
	nod*p=new nod;
	p->vf=b;
	p->val=c;
	p->next=g[a];
	g[a]=p;
}
void dijsktra()
{
	int coada[nn],v[nn];
	for(int i=1;i<=n;++i)
	{
		d[i]=inn;
		v[i]=0;
	}
	int st,dr;
	st=dr=1;
	d[1]=0;
	coada[1]=1;
	v[1]=1;
	while(st<=dr)
	{
		cout<<coada[st]<<" ";
		cin.get();
		int k=coada[st];
		for(nod *p=g[k];p;p=p->next)
		{
			int alt=d[k]+p->val;
			if(alt<d[p->vf])
				d[p->vf]=alt;
			if(!v[p->vf])
				{
					coada[++dr]=p->vf;
					v[p->vf]=1;
				}
		}
		++st;
	}
}
int main()
{
	int a,b,c;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for(;m;--m)
	{
		fin>>a>>b>>c;
		adauga(a,b,c);
	}
	for(int i=1;i<=n;++i)
	{
		cout<<i<<": ";
		for(nod*p=g[i];p;p=p->next)
			cout<<p->vf<<"("<<p->val<<") ";
		cout<<endl;
	}
	dijsktra();
	FILE *f=fopen("dijkstra.out","w");
	for(int i=2;i<=n;++i)
		fprintf(f,"%d ",d[i]);
	return 0;
}