#include<bits/stdc++.h>
using namespace std;
int n, m, x, y, c;
vector< pair<int,int> > a[250250];
int rez[60000];
set<int> s;
int main()
{
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y >> c;
		a[x].push_back(make_pair(y,c));
	}
	c = 1<<30;
	for (int i = 0; i <= n; i++) rez[i] = c;
	rez[1] = 0;
	s.insert(1);
	while(!s.empty())
	{	
		set<int>::iterator it1 = s.begin();
		int f = *it1;
		s.erase(s.begin());
		for (vector< pair<int,int> >::iterator it = a[f].begin(); it != a[f].end(); it++)
		{	
			if (rez[f] + it->second < rez[it->first])
			{
				rez[it->first] = rez[f] + it->second;
				s.insert(it->first);
			}
		}
	}
	for (int i = 2; i <= n; i++) cout << (rez[i] == 1 <<30 ? 0:rez[i]) << " ";
}