#include<cstdio>
#include<vector>
#include<queue>
#define N 50002

using namespace std;

vector <int> a[N],cost[N];

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;

int d[N],pred[N],inf=1<<30,m,n;

void citire();
void afis(int);
void dijkstra(int);
bool s[N];
void extinde(int,int);

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	for(int i=2 ; i<=n ; ++i)
		if(d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	printf("\n");
	//afis(n);
	return 0;
}

void citire()
{
	int x,y,c;
	scanf("%d%d ", &n,&m);
	while(m--)
	{
		scanf("%d%d%d", &x,&y,&c);
		a[x].push_back(y);
		cost[x].push_back(c);
	}
}

void dijkstra(int x)
{
	int i,c;
	for(i=1;i<=n;++i)
		d[i]=inf;
	d[x]=0;
	//s[x]=true;
	h.push(make_pair(0,x));
	while(!h.empty())
	{
		x=h.top().second;
		c=h.top().first;
		h.pop();
		if(s[x])
			continue;
		s[x]=true;
		extinde(x,c);
	}
}

void extinde(int x,int c)
{
	int y,c1;
	size_t g=a[x].size();
	for(size_t i=0;i<g;++i)
	{
		y=a[x][i];
		c1=cost[x][i];
		if(c+c1<d[y])
		{
			d[y]=c+c1 ;
			h.push(make_pair(d[y],y));
			pred[y]=x;
		}
	}
}

void afis(int x)
{
	int y;
	if(x==0)
		return;
	y=pred[x];
	afis(y);
	printf("%d ", x);
}