#include<iostream>
#include<fstream>
#include<values.h>
#include<stdio.h>
#include<vector>

using namespace std;
const int MaxL= 1000000 ;
int n,m,viz[50001];
int d[50001], mini,vali;

vector < pair<int, int> > a[50001];

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].push_back(make_pair(k,l));
		
	}
	/*for(i=1;i<=n;i++)
	{  cout <<"Nodul" <<i<<" ";
		for(j=0;j<a[i].size();j++)
			cout<<a[i][j].first<<" "<<a[i][j].second<<"-"; 
	}
	*/
	start=1;
	for(i=2;i<=n;i++)
	{   vali=MaxL;
		for(j=0;j<a[start].size();j++)
			if( a[start][j].first == i)
				 vali= a[start][j].second;
		d[i]=vali;	
		
	}
	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(k=0;k<a[poz].size();k++)
		{ j=a[poz][k].first; 
			if(viz[j]==0)
			if(d[j]>d[poz]+a[poz][k].second)
			{
				d[j]=d[poz]+a[poz][k].second;
				//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;
}