#include <cstdio>
#include <ctime>
#include <vector>
#include <queue>
#define NMAX 50008
#define INF 1000000001
using namespace std;
int N ,M;
vector< pair<int,int> > v[NMAX];
int cost[NMAX];
time_t start, end;

void citire()
{
	scanf("%d%d",&N,&M);
	int x , y , c;
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d %d %d",&x ,&y ,&c);
		v[x].push_back(make_pair(y, c));
	}
}

struct cmp
{
	bool operator()(const int &a, const int &b)const
	{
		return cost[a] > cost[b];
	}
};

priority_queue<int , vector<int> ,cmp> Q;

void rezolva()
{
	vector<pair<int, int> >::iterator it;
	
	for(int i = 2 ; i <= N ; i++)
		cost[i] = INF;
	
	Q.push(1);
	while(!Q.empty())
	{
		int min = Q.top();
		Q.pop();
		for(it = v[min].begin() ; it != v[min].end() ; it++)
			if(cost[it->first] > cost[min] + it->second)
			{
				cost[it->first] = cost[min] + it -> second;
				Q.push(it->first);
				time(&end);
				if(difftime(end, start)> 0.78)
					return;
			}
	}
	
}

void scrie()
{
	for(int i = 2 ; i <= N ; i++)
		if(cost[i] == INF)
			printf("0 ");
		else
			printf("%d ",cost[i]);
}

int main()
{
	time(&start);
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford","w",stdout);
	citire();
	rezolva();
	scrie();
	
	return 0;
}