#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMax 50005
#define oo (1 << 30)

using namespace std;


ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, D[NMax];

struct Compara
{
	bool operator() (int x, int y)
	{
		return D[x] > D[y];
	}
};

priority_queue < int, vector<int>, Compara > Coada;

vector < pair<int, int> > G[NMax];

void Citire()
{
	int M, A, B, C;

	fin >> N >> M;

	for(int i=1; i<=M; ++i)
	{
		fin >> A >> B >> C;
		G[A].push_back( make_pair(B, C) );
	}
}

void Dijkstra(int nodStart)
{
	bool inCoada[NMax];

	for(int i=1; i<=N; ++i)
		D[i] = oo;

	D[nodStart] = 0;
	Coada.push(nodStart);
	inCoada[nodStart] = true;

	while( !Coada.empty() )
	{
		int nodCurent = Coada.top();
		Coada.pop();
		inCoada[nodCurent] = false;

		for(size_t i = 0; i < G[nodCurent].size(); ++i)
		{
			int Vecin = G[nodCurent][i].first;
			int Cost = G[nodCurent][i].second;

			if(D[nodCurent] + Cost < D[Vecin])
			{
				D[Vecin] = D[nodCurent] + Cost;

				if(inCoada[Vecin] == false)
				{
					Coada.push(Vecin);
					inCoada[Vecin] = true;
				}
			}
		}
	}
}

void Afisare()
{
	for(int i=2; i<=N; ++i)
	{
		if(D[i] != oo)
			fout << D[i] << ' ';
		else fout << 0 << ' ';
	}
}

int main()
{
	Citire();
	Dijkstra(1);
	Afisare();

	return 0;
}