#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 50010
#define INF 1000000000

int d[MAXN];
int N,M;
vector<int> C[MAXN], G[MAXN];
int Q[1<<20];

void init()
{	
	int i;
	for(i=1;i<=N;i++)
		d[i]=INF;
}

void citire()
{
	FILE *fin=fopen("bellmanford.in","r");
	fscanf(fin,"%d %d",&N,&M);

	int i,j,t,z;

	for(z=1;z<=M;z++)
	{	
		fscanf(fin,"%d %d %d",&i,&j,&t);
		G[i].push_back(j);
		C[i].push_back(t);

	}
	
}

void bell()
{
	int x,i;
	int inc, sf;
	inc = sf = 0;
	d[1] = 0;
	Q[0] = 1;
	while(inc<=sf)
	{	
		x = Q[inc];
		inc++;
		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]; 
			sf++; Q[sf] = G[x][i];
			}	
			
	}		
}

void afisare()
{
	int i;
	FILE *fout=fopen("bellmanford.out","w");
	
	
	for(i=2;i<=N;i++)
		fprintf(fout,"%d ",d[i]);


	
}

int main()
{
	citire();
	init();
	bell();
	afisare();
	
return 0;
}