#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define oo (1 << 31) - 1
#define NLIM 100005

using namespace std;

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

vector < pair < int, int > > Muchii[NLIM];

struct ComparaDistante
{
	bool operator()(int x, int y)
	{
		return D[x] > D[y];
	}
};
priority_queue < int, queue < int >, ComparaDistante > Coada;

int D[NLIM];
bool InCoada[NLIM];
int N, M;

void Dijkstra(int nodStart)
{
	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 y = 0; y < Muchii[nodCurent].size(); y++)
		{
			int Vecin = Muchii[nodCurent][y].first;
			int w = Muchii[nodCurent][y].second;
			
			if (D[nodCurent] + w < D[Vecin])
			{
				D[Vecin] = D[nodCurent] + w;
				if (!InCoada[Vecin])
				{
					Coada.push(Vecin);
					InCoada[Vecin] = true;
				}
			}
		}
	}
}

void Citire()
{
	fin >> N >> M;
	int i, j, x, y, w;
	for (i = 1; i <= M; i++)
	{
		fin >> x >> y >> w;
		Muchii[x].push_back(make_pair(x, w));
	}
}

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

int main()
{
	Citire();
	Dijkstra(1);
	Afisare();
	return 0;
}