#include <cstdio>
#include <vector>
#define MaxN 50009
#define Inf 2000009

using namespace std;

vector <int> v[MaxN],cost[MaxN];
int n,m,c[2*MaxN],d[MaxN];

void cit()
{
	int i,x,y,c;
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		v[x].push_back(y);
		cost[x].push_back(c);
	}
}

void bellman_ford()
{
	int i,st=1,j,nod;
	for(i=2;i<=n;i++)
		d[i]=Inf;
	c[1]=1; 
	for(i=1;i<=st;i++)
	{
		nod=c[i];
		for(j=0;j<v[nod].size();j++)
			if(d[nod]+cost[nod][j]<d[v[nod][j]])
			{
				st++;
				c[st]=v[nod][j];
				d[v[nod][j]]=d[nod]+cost[nod][j];
			}
	}
}

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

int main()
{
	cit();
	bellman_ford();
	afis();
	return 0;
}