#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define nmax 50005
#define coada 1000000
#define pb push_back
#define inf 1<<30
vector<int> g[nmax],c[nmax];
int d[nmax];
int n,m;
void citire ()
{
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	int i,a,b,cost;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d\n", &a, &b, &cost);
		g[a].pb(b);c[a].pb(cost);
	}
	
}
void bellmanford(int nod)
{
	int sf,inc,x,i;
	for(i=1;i<=n;i++)
		d[i]=inf;
	
	queue<int> s;
	s.push(nod);
	d[nod]=0;
	while(s.size()>0)
	{
		x=s.front();
		s.pop();
		for(i=0;i<g[x].size();i++)
			if(d[g[x][i]]>d[x]+c[x][i]) 
				d[g[x][i]]=d[x]+c[x][i],s.push(g[x][i]);
	}
}
void scrie ()
{
	int i;
	freopen("dijkstra.out","w",stdout);
	for(i=2;i<=n;i++)
		if(d[i]==inf) printf("%d ", 0);
		else printf("%d ", d[i]);
	
}
int main ()
{
	citire ();
	bellmanford(1);
	scrie ();
	return 0;
}