#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ifstream fout("dijkstra.out");
const int max_size=50001;
const int inf=1e9;
int *t;
int n,m,i,a,b,c,w;
int d[max_size];
vector <pair <int,int> > graf[max_size];

int main()
{
	fin >> n >> m ;
	for (i=1;i<=m;i++)
	{
		fin >> a >> b >> c ;
		graf[a].push_back(make_pair(b,c));
	}
	for (i=1;i<=max_size;i++)d[i]=inf;
	d[1]=0;
	set <pair <int,int> > s;
	s.insert(0,1);
	while (!s.empty())
	{
		a=s.begin()->second;
		b=s.begin()->first;
		s.erase(s.begin());
		for (auto t:graf[a])
		{
			c=t->first;
			w=t->second;
			if (d[c]>d[a]+w)
			{
				if (d[c]!=inf)
				{
					s.erase(s.find(make_pair(d[c],c)));
				}
				d[c]=d[a]+w;
				s.insert(make_pair(d[c],c));
			}
		}
	}
	for (i=2;i<=n;i++)
	{
		if (d[i]==inf)d[i]=0;
		fout << d[i] <<" ";
	}
	return 0;
}