#include<cstdio>
#include<vector>
#include<utility>
#include<deque>
#include<bitset>
using namespace std;
#define nmax 50001
#define oo 1<<25
bitset<nmax> M;
int n,m,x,y,c,d[nmax];
vector<pair <int,int> > v[nmax];
deque<int> Q;
void citire()
{
	int i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		v[x].push_back(make_pair(y,c));
	}
}
void sol()
{
	int i;
	vector<pair <int,int> >::iterator it;
	for(i=2;i<=n;i++)
		d[i]=oo;
	Q.push_back(1);
	d[1]=0;
	M[1]=1;
	while(Q.size())
	{
		x=Q.front();
		for(it=v[x].begin();it!=v[x].end();it++)
		{
			if(d[x]+it->second<d[it->first])
			{
				d[it->first]=d[x]+it->second;
				if(!M[it->first])
				{
					M[it->first]=1;
					Q.push_back(it->first);
				}
			}
		}
		M[x]=0;
		Q.pop_front();
	}
	for(i=2;i<=n;i++)
	{
		if(d[i]==oo)
			printf("0 ");
		else
			printf("%d ", d[i]);
	}
}
int main()
{
	citire();
	sol();
	return 0;
}