#include<iostream>
#include<fstream>
using namespace std;
int n,m,d[1000],mini,t[1000],a[1000][1000],viz[1000];
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,poz,start,j,k,l;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=35000;
	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];
		if(d[i]<35000)
			t[i]=start;
	}
	d[start]=0;
	viz[start]=1;
	t[start]=0;
	for(i=1;i<n;i++)
	{
		mini=35000;
		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];
				t[j]=poz;
			}
	}
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	return 0;
}