#include<fstream>
#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();
		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;
}