#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

struct nod
{
	long x;
	long sum;
};
vector<nod> a[100001];
queue<long> q;
long nr,x,y,c,n,m,i,dist[100001];
nod cod;

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld %ld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&x,&y,&c);
		cod.sum=c;
		cod.x=y;
		a[x].push_back(cod);
	}
	for(i=1;i<=n;i++) dist[i]=500000000;
	dist[1]=0;
	q.push(1);
	while(!q.empty())
	{
		x=q.front();
		nr=a[x].size();
		for(i=0;i<nr;i++)
			if(dist[a[x][i].x]>dist[x]+a[x][i].sum)
			{
				dist[a[x][i].x]=dist[x]+a[x][i].sum;
				q.push(a[x][i].x);
			}
		q.pop();
	}
	for(i=2;i<=n;i++) printf("%ld ",dist[i]);
	printf("\n");
	return 0;
}