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

#define mp make_pair

using namespace std;

struct Heap
{
	int node, cost;
	Heap()
	{
		this->node = this->cost = 0;
	}
	Heap(const int &node, const int &cost)
	{
		this->node = node;
		this->cost = cost;
	}
	inline bool operator<(const Heap &other) const
	{
		return this->cost > other.cost;
	}
};

const int NMAX = 5e4 + 5;
const int INF = 2e9;
int n, m;
vector <pair <int, int> > graph[NMAX];
bitset <NMAX> seen;
priority_queue <Heap> pq;
int dist[NMAX];

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	int x, y, z;
	for (int i = 1;i <= m;++i)
	{
		fin >> x >> y >> z;
		graph[x].push_back(mp(y, z));
	}
	for (int i = 2;i <= n;++i)
		dist[i] = INF;
	pq.push(Heap(1, 0));
	Heap currNode;
	while (!pq.empty())
	{
		currNode = pq.top();
		pq.pop();
		if (seen[currNode.node] == 0)
		{
			seen[currNode.node] = 1;
			for (auto i : graph[currNode.node])
			{
				if (dist[i.first] > dist[currNode.node] + i.second)
				{
					dist[i.first] = dist[currNode.node] + i.second;
					pq.push(Heap(i.first, dist[i.first]));
				}
			}
		}
	}
	for (int i = 2;i <= n;++i)
		fout << ((dist[i] == INF) ? 0 : dist[i]) << " ";
	fin.close();
	fout.close();
	return 0;
}