#include <vector>
#include <iostream>
#include <queue>
#include <fstream>
#define INF 0x3f3f3f3f

using namespace std;

const int nmax = 50001;
const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
int D[nmax], H[nmax], N, M, x, y, c, cost, i, z;
vector<pair< int, int > > Nod[nmax];

bool P[nmax];

ifstream fin(iname);
ofstream fout(oname);

struct cmp
{
	bool operator()(const int &a, const int &b)const
	{
		if(D[a] > D[b])
			return 1;
		return 0;
	}
};

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

int main()
{
	fin >> N >> M;
	for(i = 1; i <= M; i ++)
	{
		fin >> x >> y >> c;
		Nod[x].push_back(make_pair(y, c));
	}
	for(i = 2; i <= N; i ++)
		D[i] = INF;
	
	Q.push(1);

	while(!Q.empty())
	{
		x = Q.top();
		Q.pop();
		P[x] = false;
		for(vector<pair< int, int > >::iterator it = Nod[x].begin(); it != Nod[x].end(); ++ it)
		{	
			y = it -> first;
			z = it -> second;
			if(D[y] > D[x] + z)
			{
				D[y] = D[x] + z;
				if(P[y] == false)
				{
					P[y] = true;
					Q.push(y);
				}
			}
		}
	}
	for(i = 2; i <= N; i ++)
	{
		if(D[i] == INF)
			fout << "0 ";
		else
			fout << D[i] << " ";
	}
	return 0;
}