// 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:
	friend class dijstra;
	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 element
{
	int info;
	
	int cost;
	element *next;

public:
	friend class dijstra;
	friend class multime;
	
	
	element()
	{
		next=NULL;	info=0;	cost = 0;
	}


};

class multime
{
element *first;
element *last;
public:
	friend class dijstra;
	multime()
	{
		first=NULL;	last=NULL;
	}

	multime(const multime &m)
	{
		//this->multime::multime();
		first = NULL;
		last = NULL;

		for(element *q=m.first;q;q=q->next)
		{
			insert(q->info);
		}
	}

	multime operator=(const multime &m)
	{
		this->multime::~multime();
		for(element *q=m.first;q;q=q->next)
		{
			insert(q->info);
		}
		return *this;
		
	}

friend istream & operator>>(istream &f,multime &m)
	{
		cout<<"introduceti cardinalul multimii:";
		int n;f>>n;
		for(int i=1;i<=n;i++)
		{
			int x;f>>x;m.insert(x);
		}
		return f;
	}

friend ostream& operator<<(ostream &f,multime m)
	{
		m.afiseaza();
		return f;
	}

 multime operator+(const multime m)
	{
		multime temp=m;
		
		for(element *q=first;q;q=q->next)
			temp.insert(q->info);
	//	for(element *q=m.first;q;q=q->next)
		//	temp.insert(q->info);
		
		temp.transform();
		return temp;
	}

 /*
void transform()
	{	if(first)
		if(first->next)
	for(element *q=first;q;q=q->next)
		{	
			element *t[2];t[0]=q;t[1]=q->next;
			while(t[1])
			{
				if(t[1]->info==q->info)
				{
					t[0]->next=t[1]->next;
					delete t[1];
					t[1]=t[0]->next;
				}
				else
				{
					t[1]=t[1]->next;
					t[0]=t[0]->next;
				}
			}
		}
	


	}
*/
 void transform()
	{	if(first)
		if(first->next)
	for(element *q=first;q;q=q->next)
		{	
			element *t[2];t[0]=q;t[1]=q->next;
			while(t[1])
			{
				if(t[1]->info==q->info)
				{ int ultim=0;
					t[0]->next=t[1]->next;
					if(t[1]==last)ultim=1;
					delete t[1];
					t[1]=t[0]->next;
					if(ultim==1)last=t[0];
				}
				else
				{
					t[1]=t[1]->next;
					t[0]=t[0]->next;
				}
			}
		}
	


	}
void insert(int val)
	{
		element *q= new element;	//q->next=NULL;
		q->info = val;
		if(first)
		{
			last->next=q;	
			last=q;
		}
		else
		{
			first=last=q;
		}
	}

void	operator += ( int val )
	{
		this->insert( val);
		//this->transform();
	
	}

void afiseaza()
	{
		if(!first)
			cout<<"@";
		else
			{
		for(element *q=first;q;q=q->next)
		{
			cout<<q->info<<", "; 
		}
		cout<<"\b\b  \b\b";
		//cout<<endl;
			}
	}

bool		Fiind_val(int val)
	{
		for( element *q = first;q;q=q->next)
			{
			if(q ->info == val)	return true;
			}
		return false;
	}
	

multime		operator * ( multime &ob)
	{
		multime temp;

		for( element *q=first;q; q=q->next )
			if( ob.Fiind_val( q->info) )
				temp+=q->info;

		return temp;
		
	}

multime		operator - ( multime &ob )
	{
		
		multime temp;

		for( element *q=first;q; q=q->next )
			if( !ob.Fiind_val( q->info) )
				temp+=q->info;

		return temp;
	
	}

bool	operator ==(multime &ob)
	{	

		for(element *q=first;q;q=q->next)
			if(!ob.Fiind_val(q->info))return false;

		for(element *q=ob.first;q;q=q->next)
			if(!Fiind_val(q->info))return false;

		return 1;
		
	}

	~multime()
	{
		element *q=first;
		while(q)
		{
			element *aux=q;
			q=q->next;
			delete aux;
		}
		first=NULL;
		last=NULL;
		//if(q==NULL)
			//cout<<"distrug"<<endl;
	}


};


///////////////////////////////////

class dijstra
{
int		N;
int		M;
int		*d; //pt costuri


FILE *f;
FILE *g;
multime* m;

public:
		dijstra()
		{
			f =fopen("dijkstra.in","r");
			g = fopen("dijkstra.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;
		
		m = new multime [N+1];

		for(int i=1; i<=M; i++)
		{int a,b,c;
			fscanf(f,"%d%d%d",&a,&b,&c);
			m[a]+=b;
			m[a].last->cost = c;
		}


	
	}//eof citeste
	
void	dij ()
	{
		//for(int i=1;i<=N;i++)
			//..cout<<m[i]<<endl;
		
		heap H;
		int* viz = new int[N+1];		memset(viz, 0 ,sizeof(int)*(N+1));
			
		int* father = new int[N+1];		memset(father, 0 ,sizeof(int)*(N+1));
		
		H.push(1);
		while(H.N)
		{
				int u = H.min();
				H.pop(1);
				
				
				for(element* q =m[u].first;q;q=q->next)
					if(!viz[ q->info ] && d[u]+q->cost < d[q->info] )
					{
						viz[u] = 1;
						father [q->info] = u;
						d[q->info] = d[u] + q->cost;
						H.push(q->info);
					}
		}	
		
	
		for(int i=2;i<=N;i++)
			if(d[i]!=inf)fprintf(g,"%d ",d[i]);
		else fprintf(g,"%d ",0);
		
	}//eof dij()
	
	
};//eof class dijtra


int main()
{

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


	return 0;
}