#include<iostream>
#include<fstream>
#include<values.h>
#include<stdio.h>
using namespace std;
const int MaxL= 1000000 ;
int n,m,viz[10000];
int d[100000], a[10000][10000],mini;
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,poz=0,start,j,k;
	long l;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=MaxL;
	for(i=1;i<=m;i++)
	{
		f>>j>>k>>l;
		a[j][k]=l;
	}
	start=1;
	for(i=2;i<=n;i++)
	{
		d[i]=a[start][i];
		
	}
	d[start]=0;
	viz[start]=1;
	
	for(i=1;i<n;i++)
	{
		mini=MaxL;
		for(j=1;j<=n;j++)
			if((viz[j]==0)&&(d[j]<mini))
			{
				mini=d[j];
				poz=j;
			}
		viz[poz]=1;
		for(j=1;j<=n;j++)
			if(viz[j]==0)
			if(d[j]>d[poz]+a[poz][j])
			{
				d[j]=d[poz]+a[poz][j];
				if (d[j]<0 )
					 cout <<"Eroare"<< d[poz]<<" "<<a[poz][j]<<" ---"<<i<<"  "<<j<<" "<<poz<<endl;
				
				
			}
	}
	for(i=2;i<=n;i++)
		if(d[i]>=MaxL)
			g<<0<<" ";
		else
		g<<d[i]<<" ";
	return 0;
}