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

using namespace std;

#define NMAX 50001
#define INF 50000100
int d[NMAX],b,c,in,sf,i,j,nod,n,m,k,l,a,s;
vector<int> x[NMAX], y[NMAX];
queue<int> q;
char ss[32],cc,z[NMAX];
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d%c",&n,&m,&cc);
	for (i=1;i<=m;++i)
	{
//    	gets(ss);
		fgets(ss,32,stdin);
        l=strlen(ss)-1;
        a=b=c=j=0;
        while (ss[j]!=' ')
        	a=a*10+ss[j++]-48;

        j++;
        while (ss[j]!=' ')
        	b=b*10+ss[j++]-48;

        j++;
        while (j<l)
        	c=c*10+ss[j++]-48;
        
        x[a].push_back(c);
		y[a].push_back(b);
	}
	q.push(1);
	for (i=2;i<=n;++i)
		d[i]=INF;
	z[1] = 1;
	while (!q.empty())
	{
		nod = q.front(); q.pop();
        k=(int)y[nod].size();
		for (i=0;i<k;++i)
       	{
        	a=d[nod]+x[nod][i];
			if (a<d[y[nod][i]])
			{
				d[y[nod][i]]=a;
				if (!z[y[nod][i]])
				{
					q.push(y[nod][i]);
					z[y[nod][i]]=1;
				}
			}
        }
		z[nod]=0;
	}
	for (i=2;i<=n;i++)
		if (d[i]!=INF)
			printf("%d ",d[i]);
		else
			printf("0 ");

	printf("\n");


	return 0;
}