#include <bits/stdc++.h>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector<pair<int,int> > graf[50005];
priority_queue<pair<int,int> > q; //tinem cost si nod
const int INF=1000000009;
bool viz[50005];
int ans[50005];

int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		in>>a>>b>>c;
		graf[a].push_back({b,c});
	}

	for(int i=1;i<=n+1;i++)
		ans[i]=INF;
	
	ans[1]=0;
	q.push({0,1});
	while(!q.empty())
	{
		int cost=-q.top().first;
		int nod=q.top().second;
		q.pop();
		if(viz[nod]==0)
		{
			viz[nod]=1;
			for(auto x:graf[nod])
			{
				if(viz[x.first]==0 && cost+x.second<ans[x.first])
				{
					q.push({-(cost+x.second),x.first});
					ans[x.first]=cost+x.second;
				}
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		if(ans[i]==INF)
		{
			ans[i]=0;
		}
		out<<ans[i]<<" ";
	}
	return 0;
}