#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);
	
	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;
	
}