#include<fstream>
#include<queue>
#include<cstdlib>
using namespace std;
int n,m,x0=1;
int d[50002];
struct Nod{int x,c;};
Nod *G[50002],aux;
queue <int> Q;

inline void Citire()
{
	int i,x,y,c;
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		G[i]=(Nod *)realloc(G[i],sizeof(Nod));
		G[i][0].x=G[i][0].c=0;
	}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		aux.x=y;
		aux.c=c;
		G[x][0].x++;
		G[x]=(Nod *)realloc(G[x],(G[x][0].x+1)*sizeof(Nod));
		G[x][G[x][0].x]=aux;
	}
	fin.close();
}


inline void Bellman_Ford()
{
	int i,x;
	for(i=1;i<=n;i++)
		d[i]=2000000000;
	d[x0]=0;
	Q.push(x0);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for(i=1;i<=G[x][0].x;i++)
		{
			aux=G[x][i];
			if(d[aux.x]>d[x]+aux.c)
			{
				d[aux.x]=d[x]+aux.c;
				Q.push(aux.x);
			}
		}
	}
}

inline void Afisare()
{
	int i;
	ofstream fout("bellmanford.out");
	for(i=2;i<=n;i++)
		fout<<d[i]<<' ';
	fout<<"\n";
	fout.close();
}

int main()
{	
	Citire();
	Bellman_Ford();
	Afisare();
	return 0;
}