using namespace std;
#include <cstdio>
#include <queue>
#include <string>
#define oo 0x3f3f3f3f
#define N 50001

struct nod { int x, c;nod*n;};

nod *a[N];
int d[N], n, m;

struct cmp{
	bool operator()(const int &a, const int &b)const
	{
		if(a>b) return 1;
		return 0;
	}
};
void dijkstra()
{
	priority_queue<int, vector<int>, cmp > Q;
	memset(d, oo, sizeof(d));
	d[1]=0;
	Q.push(1);
	
	while(!Q.empty())
	{
		int u=Q.top();
		Q.pop();
		
		for(nod *i=a[u]; i ; i=i->n)
			if(d[u] + i->c < d[i->x])
			{
				d[i->x]= d[u] + i->c;
				Q.push(i->x);
			}
	}

	for(int i=2;i<=n;++i) 
		if(d[i]!=oo) printf("%d ", d[i]);
		else printf("0 ");
		
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d\n", &n, &m);
	int p, q, c;
	while(m--)
	{
		scanf("%d %d %d\n", &p,&q, &c);
		nod *t=new nod;
		t->x=q;
		t->c=c;
		t->n=a[p];
		a[p]=t;
	}

	dijkstra();
	return 0;
}