#include<stdio.h>
#define max 50010
#define inf 2000000000
long d[max], vz[max], n, m;
struct elem
{       long vf, c;
	elem *urm;
}	*a[max], *q;
FILE *f, *g;

void read()
{       long i, x, y, cs;
	f=fopen("dijkstra.in", "r");
	fscanf(f, "%ld%ld", &n, &m);
	for(i=0; i<m; i++)
	{	fscanf(f, "%ld%ld%ld", &x, &y, &cs);
		q=new elem;
		q->c=cs; q->vf=y;
		q->urm=a[x];
		a[x]=q;
		if(x==1)
			d[i]=cs;
	}
	fclose(f);
}

void solve()
{       long i, c;
	for(i=1; i<=n; i++)
		if(d[i]==0)
			d[i]=inf;
	c=1;
	while(c)
	{	c=0;
		for(i=1; i<=n; i++)
		{	q=a[i];
			while(q)
			{	if(d[q->vf]>d[i]+q->c)
				{	d[q->vf]=d[i]+q->c;
					c=1;
				}
				q=q->urm;
			}
		}
	}
	for(i=1; i<=n; i++)
		if(d[i]==inf)
			d[i]=0;
}

void write()
{	long i;
	g=fopen("dijkstra.out", "w");
	for(i=2; i<=n; i++)
		fprintf(g, "%ld ", d[i]);
	fprintf(g, "\n");
	fclose(g);
}

int main()
{       read();
	return 0;
}