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

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

void swap(pair<int, int> *a, pair<int, int> *b)
{
	pair<int, int> *c = a;
	*a = *b;
	*b = *c;
}

void balance_heap(vector <pair<int, int>> &heap,int i)
{
	int less = i;
	int r = i * 2 + 1;
	int l = i * 2;
	if(heap[i].first > heap[l].first and l < heap.size())
		less = l;
	if(heap[i].first < heap[r].first and r < heap.size())
		less = r;

	if(less != i)
	{
		swap(heap[less], heap[i]);
	}
}

void insert(vector <pair<int, int>> &heap, int val, int node)
{
	if(heap.size() == 1)
		heap.push_back({val, node});
	else
	{
		heap.push_back({val, node});
		for(int i = heap.size() / 2 - 1; i >= 0; i --)
			balance_heap(heap, i);
	}
}

void del(vector <pair<int, int> > &heap)
{
	int size = heap.size();
	if(heap.size() == 1)
		heap.pop_back();
	else
	{
		swap(&heap[0], &heap[size - 1]);
		heap.pop_back();
		for(int i = heap.size() / 2 - 1; i >= 0; i --)
			balance_heap(heap, i);
	}
}

const int N = 50000;
int dist[N + 1];
void reset()
{
	for(int i = 1; i < N; i ++)
		dist[i] = INT_MAX;
}

///priority_queue<pair<int, int> > pq;
vector <pair<int, int>> pq;
vector <pair<int, int>> neighbours[N + 1];
bool verif[N];
void dijkstra(int node)
{
	reset();
	insert(pq, 0, node);
	///pq.push({0, node});
	while(!pq.empty())
	{
		pair <int, int> aux = pq[0];
		del(pq);
		///pq.pop();
		if(verif[aux.second] == false)
		{
			verif[aux.second] = true;
			for(auto next : neighbours[aux.second])
			{
				if(dist[next.second] > dist[aux.second] + next.first)
				{
					dist[next.second] = dist[aux.second] + next.first;
					insert(pq, dist[next.second], next.second);
					///pq.push({-dist[next.second], next.second});
				}
			}
		}
	}
}

int main()
{

	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a --, b --; 
		neighbours[a].push_back({c, b});
	}

	dijkstra(0);

	for(int i = 1; i < n; i ++)
	{
		if(dist[i] != INT_MAX)
			cout << dist[i] << " ";
		else
			cout << 0 << " ";
	}
	
	return 0;
}