#include<cstdio>
#include<queue>
#include<cstdlib>
using namespace std;
int n,m,x0=1;
int d[50050];
struct Nod{int x,c;};
Nod *G[50050],aux;

inline void Citire()
{
	int i,x,y,c;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		G[i]=(Nod *)realloc(G[i],sizeof(Nod));
		G[i][0].x=G[i][0].c=0;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		aux.x=y;
		aux.c=c;
		G[x][0].x++;
		G[x]=(Nod *)realloc(G[x],(G[x][0].x+1)*sizeof(Nod));
		G[x][G[x][0].x]=aux;
	}
}


inline void Bellman_Ford()
{
	int i,x;
	for(i=1;i<=n;i++)
		d[i]=2000000000;
	d[x0]=0;
	queue <int> Q;
	Q.push(x0);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for(i=1;i<=G[x][0].x;i++)
		{
			aux=G[x][i];
			if(d[aux.x]>d[x]+aux.c)
			{
				d[aux.x]=d[x]+aux.c;
				Q.push(aux.x);
			}
		}
	}
}

inline void Afisare()
{
	int i;
	freopen("dijkstra.out","w",stdout);
	for(i=2;i<=n;i++)
	{
		if(d[i]!=2000000000)
			printf("%d ",d[i]);
		else
			printf("0 ");
	}
	printf("\n");
}

int main()
{	
	Citire();
	Bellman_Ford();
	Afisare();
	return 0;
}