#include <stdio.h>
#include <string.h>
#define oo 0x3f3f3f3f // < = > (1 << 30)
#define nmax 50005 
#define nmax2 250005
using namespace std;


class Heap
{ 
public:
    int *values;
    int *nodes;
    int *poz;
	int capVect;
	
	int dimVect, numere;
    Heap(int capVect);
	
    ~Heap();
 
    int parent(int poz);
 
    int leftSubtree(int poz);
 
    int rightSubtree(int poz);
 
    void pushUp(int poz1,int poz2);   
 
    void Insert_heap(int b,int x);

    int minim(int a,int b);

    void erase(int k);	
};

Heap::Heap(int capVect)
{
	this-> capVect = capVect;
	this->dimVect = -1;
	this->numere = -1;
	values = new int[capVect];	
	nodes = new int[capVect];	
	poz = new int[capVect];	
}

Heap::~Heap()
{
   delete[] values;
}

int Heap::parent(int poz)
{
    return (poz - 1) / 2;
}

int Heap::leftSubtree(int poz)
{
    if(poz * 2 +1 <= dimVect)
		return poz * 2 +1;
	else return -1;
}

int Heap::rightSubtree(int poz)
{
  	if(poz * 2 +2 <= dimVect)
		return poz * 2 +2;
	else return -1;
}

void Heap::pushUp(int poz1,int poz2)
{
int aux;
	aux = values[poz1];
	values[poz1] = values[poz2];
	values[poz2] = aux; 
	
	aux = nodes[poz1];
	nodes[poz1] = nodes[poz2];
	nodes[poz2] = aux; 
	
	aux = poz[poz1];
	poz[poz1] = poz[poz2];
	poz[poz2] = aux; 
}

void Heap::Insert_heap(int b,int x)
{
int poz_curent, poz_parinte;

    if(dimVect == -1)
	{
	values[0] = x;
	nodes[0] = b;
	poz[b] = 0;
	dimVect = 0;
	numere = 0;
	}
	else 
	{
	numere++;
	values[++dimVect] = x;
	nodes[dimVect] = b;
	poz[ b ] = dimVect; 
	
	poz_curent = dimVect;

	poz_parinte =  parent(poz_curent);
	while( values[ poz_parinte  ] > values[ poz_curent ] )
	{
		pushUp( poz_curent,  poz_parinte);
		poz_curent = poz_parinte;
		
		if(poz_curent == 0)
			break;
		poz_parinte =  parent(poz_curent);		
	}	
	}
}

int Heap::minim(int a, int b)
{
	if(values[a] < values[b]) return a;
	return b;   	
}

void Heap::erase(int k)
{
int poz_curent,aux,poz_stanga,poz_dreapta,fiu_cel_mare;
		
	if( k  != 0 )
	{
		k = poz[ k ];
	}

	aux = values[dimVect];
	values[dimVect] = values[k];
	values[k] = aux;
	
	aux = nodes[dimVect];
	nodes[dimVect] = nodes[k];
	nodes[k] = aux;
	
	aux = poz[dimVect];
	poz[dimVect] = poz[k];
	poz[k] = aux;

	dimVect--;
	poz_curent = k;

	poz_dreapta = rightSubtree(poz_curent);
	poz_stanga = leftSubtree(poz_curent);
	

	if(poz_dreapta < 0 && poz_stanga > 0)
		fiu_cel_mare = leftSubtree(poz_curent);
	else if(poz_dreapta > 0 && poz_stanga < 0)
		fiu_cel_mare = rightSubtree(poz_curent);
	else
		fiu_cel_mare = minim(poz_stanga,poz_dreapta);

	
	while( values[fiu_cel_mare] < values[poz_curent])
	{
		pushUp(fiu_cel_mare,poz_curent);
		poz_curent = fiu_cel_mare;

	poz_dreapta = rightSubtree(poz_curent);

	poz_stanga = leftSubtree(poz_curent);
	
	if(poz_dreapta < 0 && poz_stanga > 0)
		fiu_cel_mare = leftSubtree(poz_curent);
	else if(poz_dreapta > 0 && poz_stanga < 0)
		fiu_cel_mare = rightSubtree(poz_curent);
	else if(poz_dreapta > 0 && poz_stanga > 0)
		fiu_cel_mare = minim(poz_stanga,poz_dreapta);
	else break;
	}	
}


FILE *f = fopen("dijkstra.in","r"), *g = fopen("dijkstra.out","w");
int best[ nmax ], viz[ nmax ], M[ nmax ], length, n, m; 

struct graf
{
	int nod, cost;
	graf *next;	
};
graf *a[nmax];

void citire()
{
	int x, y, z;
	
	fscanf( f, "%d %d", &n, &m ); 
	
    for ( int i = 1; i <= m; ++i )
    {
        fscanf( f, "%d %d %d", &x, &y, &z);
		graf *q = new graf;
		q->nod = y;
		q->cost = z;
		q->next = a[x];
		a[ x ] = q;
    }
	fclose(f);
}

void dijkstra_heap( int start, int stop )
{
	graf *q, *p;
	Heap H(nmax2);
	memset(viz,0,sizeof(viz));
	memset(best,oo,sizeof(best));
	p = new graf;
	
	
	viz[ start ] = 1;
	best[ start ] = 0;
	M[ ++length ] = start;
	q = a[ start ];
	p->nod = start; 
	
	do
	{	
		//actualizam vecinii
		while ( q )
		{
			if ( best[ q->nod ] > q->cost + best[ p->nod ] )
			{
				if ( !viz[ q->nod ] )
				{
					H.Insert_heap( q->nod, q->cost + best[ p->nod ] );
					viz[ q->nod ] = 1;
				}
				else
				{
					H.erase(q->nod); 
					H.Insert_heap( q->nod,  q->cost + best[ p->nod ] );
				}
				best[ q->nod ] =  q->cost + best[ p->nod ] ;
			}	
			q = q -> next;
		}
		
	if( H.dimVect == -1 )
		break;
	p->cost = (int)H.values[0];
	p->nod = H.nodes[0];	
	H.erase(0);
	
	M[ ++length ] = p->nod;
	q = a[ p->nod ];
	}while ( 1 );
}

void afisare()
{
	//afisam lungimea unui drum minim de la nodul de start = 1 la nodul i+1.
	for ( int i = 2; i <= n; ++i )
	{
		if(best[ i ] == oo)
			fprintf( g,"0 ");
		else
		fprintf( g, "%d ",best[ i ] );
	}
	fprintf(g,"\n");
	fclose(g);
}
int main()
{
	citire();
	dijkstra_heap(1,n);
	afisare();
return 0;
}