/*#include <cstdio>
#include <set>
#include <vector>

using namespace std;

#define file_in "dijkstra.in"
#define file_out "dijkstra.out"

#define f first
#define s second

#define Nmax 101000

vector<int> G[Nmax],C[Nmax];
int d[Nmax];
int n,m;
set< pair<int,int> > t;
char s[1000];

void solve()
{
	int i,val,nod;
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	
	t.insert(make_pair(0,1));
	
	while(t.size()>0)
	{
		val=(*t.begin()).first;
		nod=(*t.begin()).second;
		
		t.erase(*t.begin()); 

		
		for (i=0;i<G[nod].size();++i)
		{
			if (d[G[nod][i]]>C[nod][i]+val)
				d[G[nod][i]]=C[nod][i]+val,
				t.insert(make_pair(d[G[nod][i]],G[nod][i]));
		}
	}
}
	
	

int main()
{
	int i,a,b,c,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	//scanf("%d %d\n", &n ,&m);
	gets(s);
	j=0;
	n=m=0;
	while(s[j]>='0' && s[j]<='9')
	{
		n=n*10+s[j]-'0';
		j++;
	}
	j++;
	while(s[j]>='0' && s[j]<='9')
	{
		m=m*10+s[j]-'0';
		j++;
	}
	
	for (i=1;i<=m;++i)
	{
		//scanf("%d %d %d", &a, &b, &c);
		
		gets(s);
		j=0;
		int l=strlen(s);
		a=b=c=0;
		while(s[j]>='0' && s[j]<='9')
		{
			a=a*10+s[j]-'0';
			j++;
		}
		j++;
		while(s[j]>='0' && s[j]<='9')
		{
			b=b*10+s[j]-'0';
			j++;
		}
		j++;
		while(s[j]>='0' && s[j]<='9')
		{
			c=c*10+s[j]-'0';
			j++;
		}
		j++;
		G[a].push_back(b);
		C[a].push_back(c);
	}
	
	solve();
	
	for (i=2;i<=n;++i)
	     if (d[i]==0x3f3f3f3f)
			 printf("0 ");
		 else
			 printf("%d ", d[i]);
		 
	fclose(stdin);	 
	fclose(stdout);	 
	
	return 0;
	
}
*/

#include <cstdio>
#include <vector>

using namespace std;


#define file_in "dijkstra.in"
#define file_out "dijkstra.out"

#define Nmax 50101

int n,m,i,x[5*Nmax],y[5*Nmax],c[5*Nmax],d[Nmax],j;

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	
	scanf("%d %d", &n, &m);
	
	memset(d,0,sizeof(d));

	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &x[i], &y[i], &c[i]);
		
		if (x[i]==1)
			d[y[i]]=c[i];
	}
	
	for (i=2;i<=n;++i)
		 if (d[i]==0)
			 d[i]=0x3f3f3f3f;
		 
	
	int ok=1;
	while(ok)
    {
	   ok=0;
	   
	   for (i=1;i<=m;++i)
		    if (d[y[i]]>d[x[i]]+c[i])
				d[y[i]]=d[x[i]]+c[i],
				ok=1;
	}
	
	
	for (i=2;i<=n;++i)
		 if (d[i]==0x3f3f3f3f)
			 printf("0 ");
		 else
			 printf("%d ", d[i]);
		 
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}