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

using namespace std;

const int DIM = 5e4 + 10;
const int INF = 2e9;
int n, m;
vector <pair <int, int> > graph[DIM];
int dist[DIM];

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

priority_queue <heap> pq;

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