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

#define input "dijkstra.in"
#define output "dijkstra.out"
#define NMAX 50005
#define DAN_BILZERIAN (1 << 30)

using namespace std;

ifstream in(input);
ofstream out(output);

struct muchie
{
	int dest, cost;
};
vector < muchie > muchii[NMAX];

bool uz[NMAX];
int dist[NMAX], N, M;

class Bilzerian
{
	public:
		bool operator() (int x, int y)
		{
			return dist[x] > dist[y];
		}
};
priority_queue < int, vector < int >, Bilzerian > coada;

void Read_Data()
{
	in >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int x, y, cost;
		in >> x >> y >> cost;
		muchii[x].push_back({ y, cost });
	}
	for (int i = 2; i <= N; i++)
		dist[i] = DAN_BILZERIAN;
}

void Dijkstra()
{
	coada.push(1);
	uz[1] = 1;
	while (!coada.empty())
	{
		int nod = coada.top();
		int cost = dist[nod];
		coada.pop();
		uz[nod] = 0;
		for (unsigned i = 0; i < muchii[nod].size(); i++)
		{
			int new_nod = muchii[nod][i].dest;
			int new_cost = muchii[nod][i].cost;
			if (cost + new_cost < dist[new_nod])
			{
				dist[new_nod] = cost + new_cost;
				if (!uz[new_nod])
				{
					uz[new_nod] = 1;
					coada.push(new_nod);
				}
			}
		}
	}
	for (int i = 2; i <= N; i++)
	if (dist[i] == DAN_BILZERIAN) out << 0 << " ";
	else out << dist[i] << " ";
}

int main()
{
	Read_Data();
	Dijkstra();
	return 0;
}