#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

#define oo 2147483647
#define to first
#define cost second
#define mp make_pair
#define DIM 8192

int N,M;
vector<pair<int,int> >a[50001];
int d[50001];
char p[8192];
int poz;

struct cmp
{	bool operator ()(int i,int j)
	{	if(d[i] < d[j]) return 1;
		return 0;
	}
};
priority_queue<int,vector<int>,cmp>q;

void read(int &x)
{	x = 0;
	while(p[poz] < '0' || p[poz] > '9')
	{	poz++;
		if(poz == DIM) fread(p,1,DIM,stdin) , poz = 0;
	}
	while(p[poz] >= '0' && p[poz] <= '9')
	{	x = x * 10 + p[poz] - '0' , poz++;
		if(poz == DIM) fread(p,1,DIM,stdin) , poz = 0;
	}
}

void dijkstra()
{	int x,i;
	bool in[50001];
	for(i = 2; i <= N; i++)
		d[i] = oo;
	d[1] = 0; q.push(1); in[1] = 1;
	while(!q.empty())
	{	x = q.top(); q.pop(); in[x] = 0;
		for(int k = 0; k < a[x].size(); k++)
			if(d[a[x][k].to] > d[x] + a[x][k].cost)
			{	d[a[x][k].to] = d[x] + a[x][k].cost;
				if(!in[a[x][k].to])
				{	in[a[x][k].to] = 1; q.push(a[x][k].to); }
			}
	}
	for(i = 2; i <= N; i++)
		if(d[i] != oo) printf("%d ",d[i]);
		else printf("%d ",0);
}

int main()
{	int i,j,x,y,c;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read(N); read(M);
	for(; M--;)
	{	read(x); read(y); read(c);
		a[x].push_back(mp(y,c));
	}
	dijkstra();
	return 0;
}