#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define max_size 20000005
int x, y, z, N, M;
int dis[50005], viz[50005];
vector < pair <int, int> > graph[50005];
priority_queue <pair <int, int> > myheap;
void dijkstra(int x)
{
	myheap.push(make_pair(0, x));
	for (int i = 1; i <= N; i++)
		dis[i] = max_size;
	dis[x] = 0;
	while (!myheap.empty())
	{
		pair <int, int> p = myheap.top();
		myheap.pop();
		int index = p.second;
		int cost = -p.first;
		if (viz[index] == 0)
		{
			viz[index] = 1;
			dis[index] = cost;
			for (int i = 0; i < graph[index].size(); i++)
			{
				int vecin = graph[index][i].first;
				if (dis[vecin] > dis[index] + graph[index][i].second)
				{
					dis[vecin] = dis[index] + graph[index][i].second;
					myheap.push(make_pair(-dis[vecin], vecin));
				}
			}
		}
	}
}
int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y >> z;
		graph[x].push_back(make_pair(y, z));
	}
	dijkstra(1);
	for (int i = 2; i <= N; i++)
	{
		if (dis[i] == max_size) dis[i] = 0;
		fout << dis[i] << " ";
	}
	system("pause");

}