#include<fstream>
#include<iostream>
#include<queue>
using namespace std;

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

#define MAX 50001

struct Node
{
	int v;
	int c;
	Node *next;
}*A[MAX];

int D[MAX], N, M, i, x, y, c;

class CompareClass
{
public:
	bool operator() (Node &i, Node &j)
	{
		return (i.c > j.c);

	}
};

priority_queue<Node, vector<Node>, CompareClass> q;

void add_to_graph(int x, int y, int c)
{
	Node *p = new Node;
	p->v = y;
	p->c = c;
	p->next = A[x];
	A[x] = p;
}

void dijkstra(int s)
{
	Node *p, temp, temp_1;

	D[s] = 0;
	temp.v = s;
	temp.c = 0;
	q.push(temp);
	while (q.size())
	{
		temp = q.top();
		p = A[temp.v];
		q.pop();

		if (D[temp.v] < temp.c)
			continue;

		while (p)
		{
			if (temp.c + p->c < D[p->v])
			{
				D[p->v] = temp.c + p->c;
				temp_1.v = p->v;
				temp_1.c = D[p->v];
				q.push(temp_1);
			}
			p = p->next;
		}
	}
}

int main()
{
	in >> N >> M;
	for (i = 1; i <= M; ++i)
	{
		in >> x >> y >> c;
		add_to_graph(x, y, c);
	}
	for (i = 1; i <= N; ++i)
		D[i] = 1 << 30;

	dijkstra(1);

	for (i = 2; i <= N; ++i)
		if (D[i] != (1 << 30))
			out << D[i] << " ";
		else
			out << 0 << " ";

	return 0;
}