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

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector<pair<int,int>> g[50001];
int n,m,a,b,c;
int d[50001];
int main()
{
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		d[i]=2e9;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		g[a].push_back({b,c});
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	q.push({0,1});
	d[1]=0;
	while(!q.empty())
	{
		pair<int,int> a=q.top();
		q.pop();
		if(d[a.second]!=a.first)
			continue;
		for(auto &i:g[a.second])
		{
			if(d[i.first]>a.first+i.second)
			{
				d[i.first]=a.first+i.second;
				q.push({d[i.first],i.first});
			}
		}
	}	
	for(int i=2;i<=n;i++)
		cout<<d[i]<<' ';
	return 0;
}