#include<cstdio>
#include<vector>
#include<queue>
#define N 50001
#define M 250001
#define OO 1<<18
using namespace std;
vector <int> a[N],cost[M];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;
int d[N],pred[N],n,m;
bool s[N];
void extinde (int, int);
void citire ()
{
	int x,y,c;
	scanf ("%d%d",&n,&m);
	for (int i=1 ; i<=m ; ++i)
	{
		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]=OO;
	}
	d[x]=0;
	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 afisare ()
{
	int i;
	for(i=2;i<=n;++i)
	{
		if(d[i]!=OO)
            printf("%d ",d[i]);
        else
            printf("0 ");
	}
}
int main () 
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	citire ();
	dijkstra (1);
	afisare();
	return 0;
}