#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void read();
void solve();
void check();
void print();

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;
const int oo = 0x3f3f3f;

int n, m;
int dist[MAX_NODES];
int inQueue[MAX_NODES];
vector<pair<int, int> > List[MAX_NODES];
/*
struct node
{
	int right;
	int cost;
	node(int a, int b) { right = a; cost = b; };
};
*/
int main()
{
	read();
	solve();
	check();
	print();

	return 0;
}

void read()
{
	ifstream f("dijkstra.in", fstream::in);

	f >> n >> m;
	int left, right, cost;

	for (int i = 1; i <= m; ++i)
	{
		f >> left >> right >> cost;

		List[left].push_back(make_pair(right, cost));
	}
};

void solve()
{
	queue<int> Q;
	
	for (int i = 1; i <= n; ++i)
		dist[i] = oo;

	int start_node = 1;
	dist[start_node] = 0;
	Q.push(start_node);
	inQueue[start_node] = true;

	int nod;

	while (!Q.empty())
	{
		nod = Q.front();
		Q.pop();
		inQueue[nod] = false;

		for (vector<pair<int, int> >::iterator it = List[nod].begin(); it != List[nod].end(); ++it)
			if (dist[it->first] > dist[nod] + it->second)
			{
				dist[it->first] = dist[nod] + it->second;
				if (!inQueue[it->first])
				{
					Q.push(it->first);
					inQueue[it->first] = true;
				}

			}
	}
};

void check()
{
};

void print()
{
	ofstream f("dijkstra.out", fstream::out);

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