#include<cstdio>
#include<vector>
#include<bitset>
#include<algorithm>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define n_max 50005
#define INF 1 << 30
#define FOR(prim,p) \
    for(pnod p = prim; p; p = p->urm)
using namespace std;

int n,m;

typedef struct nod {
	int inf, cost;
	nod * urm;
} *pnod;

pnod v[n_max];

vector <int> dist(n_max,INF), post(1);

bitset <n_max> uz;




void add( pnod &p, int x, int c)
{
	pnod q = new nod;
	
	q->inf = x;
	q->cost = c;
	q->urm = p;
	
	p=q;
}



void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	int x,y,c;
	
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&c);
		
		add(v[x],y,c);
	}
	
	fclose(stdin);
}




void dfs(int x)
{
	uz[x] = 1;
	
	FOR(v[x],p)
		if(!uz[p->inf])
			dfs(p->inf);
	
	post.push_back(x);
}




void rezolva()
{
	for(int i=1;i<=n;i++)
		dfs(i);
	
	dist[1] = 0;
	
	for(int i=n;i;i--)
		FOR(v[post[i]],p)
			if(dist[post[i]] + p->cost < dist[p->inf])
				dist[p->inf] = dist[post[i]] + p->cost;
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	for(int i=2;i<=n;i++)
		printf("%d ",dist[i] == INF ? 0 : dist[i]);

	fclose(stdout);
}




int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}