#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <cstring>

#define Nmax 50005
#define INF 0x3f3f3f3f

using namespace std;

int DP[Nmax], N, M;

vector<pair<int,int> > G[Nmax];
queue<int> Q;
bitset<Nmax> inQ;

void Read()
{
	scanf("%d%d",&N,&M);
	int a,b,c;
	for(int i = 1;  i<= M; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		G[a].push_back({c,b});
	}
	memset(DP,INF,sizeof(DP));
}

void Bellman_ford(int k)
{
	Q.push(k);
	DP[k] = 0;
	while(!Q.empty())
	{
		k = Q.front();
		Q.pop();
		inQ[k] = false;
		for(auto it : G[k])
			if(DP[it.second] > DP[k] + it.first)
			{
				DP[it.second] = DP[k] + it.first;
				if(inQ[it.second]) continue;
				inQ[it.second] = true;
				Q.push(it.second);
			}
	}
	for(int i = 2; i <= N; ++i)
		if(DP[i] >= INF) printf("0 ");
		else printf("%d ",DP[i]);
}

int main()
{
	freopen("bellmanf.in","r",stdin);
	freopen("bellmanf.out","w",stdout);

	Read();
	Bellman_ford(1);

	return 0;
}