#include <bits/stdc++.h>
using namespace std;
struct ff
{
	long long u,v,w;
};
long long n,m,sx,dis[500005];
vector<ff> s;
vector<long long> a[500005]; 
bool b[500005];
priority_queue<pair<long long,long long> > ab;
int main()
{
	cin>>n>>m;
    sx=1;
	for(long long i=1;i<=m;i++)
	{
		ff e;
		cin>>e.u>>e.v>>e.w;
		s.push_back(e);
	}
	for(long long i=0;i<m;i++) a[s[i].u].push_back(i);
	for(long long i=1;i<=n;i++) dis[i]=1e10;
	dis[sx]=0;
	ab.push(make_pair(dis[sx],sx));
	while(!ab.empty())
	{
		long long u=ab.top().second;
		ab.pop();
		if(b[u]==1) continue;
		b[u]=1;
		for(long long j=0;j<a[u].size();j++)
		{
			long long v=s[a[u][j]].v;
			long long w=s[a[u][j]].w;
			if(b[v]==0&&dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				ab.push(make_pair(-dis[v],v));
			}
		}
	}
	for(long long i=1;i<=n;i++)  
    {
        if(dis[i]==1e10) cout<<-1;
        else cout<<dis[i]<<" ";
    }
 	return 0;
}