#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

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

using PI = pair<int, int>;
using VI = vector<int>;

vector<vector<PI>> G; // graful citit

const int Dim = 5e4 + 10, Inf = 0x3f3f3f3f;
VI D, cnt;
int n, m;

void CitesteGraf();
void Dijkstra(int x);
void AfiseazaDrum();

int main()
{
	CitesteGraf();
	Dijkstra(1);

	AfiseazaDrum();
}

void CitesteGraf()
{
	fin >> n >> m;

	G = vector<vector<PI>>(n + 1);
	cnt = VI(n + 1);

	for (int i = 1, x, y, w; i <= m; ++i)
	{
		fin >> x >> y >> w;
		G[x].emplace_back(y, w);
	}
}

void Dijkstra(int x)
{
	queue<int> Q;
	vector<bool> inQ(n + 1);
	D = VI(n + 1, Inf);

	D[x] = 0;
	Q.push(x); // O(1) , niciun obiect nou nu trebuie creat
	inQ[x] = 1;

	while (!Q.empty())
	{
		x = Q.front();
		Q.pop();
		inQ[x] = 0;

		for(auto& pair : G[x])
		{
			auto& y = pair.first;
			auto& w = pair.second;

			if (D[y] > D[x] + w)
			{
				D[y] = D[x] + w;

				if (!inQ[y])
				{
					Q.push(y);
					inQ[y] = 1;
				};
			}
		}
	}
}

void AfiseazaDrum()
{
	for (int i = 2; i <= n; ++i)
		if (D[i] != Inf)
			fout << D[i] << ' ';
		else
			fout << "0 ";
}