#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define nmax 50005
#define coada 10000000
#define pb push_back
#define inf 1<<30
vector<int> g[nmax],c[nmax];
int d[nmax];
queue<int> s;
int n,m;
void citire ()
{
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	int i,a,b,cost;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>cost;
		g[a].pb(b);c[a].pb(cost);
	}
	
	fin.close();
}
void bellmanford(int nod)
{
	int sf,inc,x,i;
	for(i=1;i<=n;i++)
		d[i]=inf;
	
	s.push(nod);
	d[nod]=0;
	while(s.size()>0)
	{
		x=s.front();
		s.pop();
		for(i=0;i<g[x].size();i++)
			if(d[g[x][i]]>d[x]+c[x][i]) 
				d[g[x][i]]=d[x]+c[x][i],s.push(g[x][i]);
	}
}
void scrie ()
{
	int i;
	ofstream fout("bellmanford.out");
	for(i=2;i<=n;i++)
		 fout<<d[i]<<' ';
	fout.close();
}
int main ()
{
	citire ();
	bellmanford(1);
	scrie ();
	return 0;
}