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

using namespace std;

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


#define p first
#define c second

typedef pair<int, int> Node;

struct compare
{
	bool operator() (const Node &n1, const Node &n2)
	{
		return n1.c > n2.c;
	}
};

priority_queue<Node, vector<Node>, compare> PQ;
vector<Node> G[50010];

int D[50010], N, M;

void Dijkstra(int S)
{
	for (int i = 2;i <= N;++i)
		D[i] = 1 << 30;
	D[S] = 1;
	PQ.push(make_pair(S, 0));

	while (PQ.size())
	{
		Node e = PQ.top();
		PQ.pop();

		for (int i = 0;i < G[e.p].size();++i)
			if (e.c + G[e.p][i].c < D[G[e.p][i].p])
			{
				D[G[e.p][i].p] = e.c + G[e.p][i].c;

				PQ.push(make_pair(G[e.p][i].p, D[G[e.p][i].p]));
			}

	}


}



int main()
{
	in >> N >> M;

	for (int i = 1;i <= M;++i)
	{
		int x, y, cost;

		in >> x >> y >> cost;
		G[x].push_back(make_pair(y, cost));
	}
	Dijkstra(1);
	for (int i = 2;i <= N;++i)
		if (D[i] == (1 << 30))
			out << "0 ";
		else
			out << D[i] << " ";

}