#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

#define nmax 50002
#define inf 1000000000

typedef struct structura{int vec,pret;};
int n,m,cost[nmax],l[nmax]; structura x;
vector <structura> nod[nmax];
queue <int> q;

void citire()
{
	freopen("dijkstra.in","r",stdin);
	
	scanf("%d%d",&n,&m); int i,j;
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&j,&x.vec,&x.pret);
		nod[j].push_back(x);
	}
	for(i=1;i<=n;i++)
		l[i]=nod[i].size();
}
void init()
{
	for(int i=2;i<=n;i++)
		cost[i]=inf;
}
int main()
{
	int i,p,s;
	citire();init();
	q.push(1);
	while(!q.empty())
	{
		p=q.front();q.pop();
		for(i=0;i<l[p];i++)
		{
			x=nod[p][i];
			s=cost[p]+x.pret;
			if(cost[x.vec]>s)
			{
				q.push(x.vec);
				cost[x.vec]=s;
			}
		}
	}
	freopen("dijkstra.out","w",stdout); 
	for(i=2;i<=n;i++)
		if(cost[i]==inf) printf("%d ",0);
		else printf("%d ",cost[i]);
	return 0;
}