#include<iostream>
#include<fstream>
using namespace std;
long n,m;
struct muchie
{
	long x,y,c;
}a[25000];
long d[50001];
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	long i;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		//scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		f>>a[i].x>>a[i].y>>a[i].c;
		if(a[i].x==1)
			d[a[i].y]=a[i].c;
	}
	for(i=1;i<=n;i++)
		if(d[i]==0)
			d[i]=250010;
		int gata=0;
	while(!gata)
	{
		gata=1;
		for(i=1;i<=m;i++)
			if(d[a[i].y]>d[a[i].x]+a[i].c)
			{
				gata=0;
				d[a[i].y]=d[a[i].x]+a[i].c;
			}
	}
	for(i=2;i<=n;i++)
		if(d[i]>=32000)
			g<<"0 ";
		else
			g<<d[i]<<" ";
		return 0;}