// dijkstra.cpp : Defines the entry point for the console application.
//


#include <iostream>
using namespace std;

const int inf = 1<<30;

class heap
{

int *poz;
int nr_poz;

int*	H;
int		N;

public:
	
	heap()
		{	
			poz = new int [200000];
			nr_poz =0;

			H = new int [200000];
			N = 0;
		}



int		father ( int nod )
	{
		return nod/2;
	}

int		left_son( int nod )
	{
		return nod * 2;
	}

int		right_son( int nod )
	{
		return nod * 2 + 1;
	}


int		min ()
	{
		return H[1];
	}

int		min_son ( int k )
	{
		int		son = 0;

		if ( left_son(k)<=N )
		{
		 son = left_son(k);

			if ( right_son(k)<=N && H[ right_son(k) ] < H[ son ] )
				son = right_son(k);
			}

	return son;		
	}

void	sift (int k)
	{
		int		son = 0;

		do
			{
				son = min_son ( k );
				
				if( H[ k ] < H [ son ] )
					son = 0;

				if( son )
					{
						int temp;
						temp = H [ son ];
						H [ son ] = H [ k ];
						H[ k ] = temp;

						k = son;
					}
				
			
			}while(son);

	
	}

int		percolate ( int k )
	{
		int key = H[ k ];		

		while ( k>1 && H[father(k)]>H[k])
			{
				H[ k ] = H [ father(k) ];
				k = father(k);
				H[k] = key;
			}
		return k;
	}

int		push( int x)
	{
		H [ ++N ] = x;
		return percolate ( N );

	}

int		pop ( int k )
	{
		int temp = H[k];

		H [ k ] = H [N];	N--;

		if (k>1 && H[father(k)]>H[k])
			percolate ( k );
		else
			sift( k );
	
		return temp;
	}

void	afiseaza (FILE *g)
	{
		for( int i=1; i<= N; i++)
			fprintf(g,"%d ", H[i]);
	}


void	ruleaza(FILE * f, FILE *g)
	{
		int n;
		fscanf(f, "%d",&n);
		int x = 0;
		for(int i=1 ; i<=n; i++)
			{
				fscanf(f, "%d", &x );
				if(x ==1 )
					{
						int y;	fscanf(f,"%d",&y);
						
							poz[++nr_poz] = push(y);
					}
				else
					if(x==2)
						{
							int y;	fscanf(f,"%d",&y);

							fprintf(g,"%d\n",pop(poz[y]));
						}
					else
						fprintf(g,"%d\n",min());
			}
	}


}; //eof class heap

class muchie
{
int		u;
int		v;

int		cost;
public:
	friend class listaMuchii;
	friend class dijstra;
	muchie()
	{
		cost = inf;
		u=v=0;
	}
	
	
};//eof class muchie

class listaMuchii
{

muchie *ls;
public:
	friend class dijstra;
	listaMuchii()
		{
			ls=NULL;
		}
	listaMuchii (int m)
		{
			ls = new muchie [ m ];
		}
	muchie&	operator[](int x)
		{
			return ls[x];
		}

};

class dijstra
{
int		N;
int		M;
int		*d;

FILE *f;
FILE *g;
listaMuchii l;

public:
		dijstra()
		{
			f =fopen("dijstra.in","r");
			g = fopen("dijstra.out","w");
			if(f==NULL){cout<<"eroare";exit(0);}

			N=0;
			M=0;
			d = NULL;
		}

void	citeste()
	{
		fscanf(f,"%d%d",&N,&M);

		d = new int [N+1];
		d[1] = 0;
		for(int i=2; i<=N; i++)
			d [ i ] = inf;
		
		l.listaMuchii::listaMuchii(M+1);

		for(int i=1; i<=M; i++)
			fscanf(f,"%d%d%d",&l[i].u,&l[i].v,&l[i].cost);


	
	}//eof citeste
	
void	dij ()
	{
		int* viz = new int[N+1];		memset(viz,0,sizeof(int)*(N+1));

		viz[1] = 1;

		for(int i=1; i<=M;i++)
			if(!viz [l[i].v] )
				{
					if( d[ l[i].v ] > d[ l[i].u  ] +l[i].cost)
						d[ l[i].v ] =d[ l[i].u  ] +l[i].cost;
				}



		for(int i=2;i<=N;i++)
			fprintf(g,"%d ",d[i]);

	}
	
	
};//eof class dijtra


int main()
{

dijstra D;
D.citeste();
D.dij();


	return 0;
}