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