// dijkstra n2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <fstream>
#define pb push_back
#define oo 99999999

using namespace std;

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

vector<pair<int, int> >graf[50005];
int n, m;
int dist[50005];
bool viz[50005];

void read()
{
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		graf[x].pb({ y, c });
	}
	for (int i = 1; i <= n; i++)
		dist[i] = oo;
}

void dijkstra()
{
	dist[1] = 0;
	int mnm;
	for (int i = 1; i <= n; i++)
	{
		int mnm = oo;
		int idx = -1;
		for (int j = 1; j <= n; j++)
		{
			if (!viz[j] && dist[j] < mnm)
			{
				mnm = dist[j];
				idx = j;
			}
		}
		viz[idx] = true;
		for (auto j:graf[idx])
			if (dist[idx] + j.second < dist[j.first])
			{
				dist[j.first] = dist[idx] + j.second;
			}
	}
}

void display()
{
	for (int i = 2; i <= n; i++)
		if (dist[i] == oo)
			out << "0" << " ";
		else
			out << dist[i] << " ";
}




int main()
{
	read();
	dijkstra();
	display();

	return 0;

}