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

#define inf 1001
#include <cstdio>
#include <fstream>
#include <malloc.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct graf
{
	unsigned long x,y;
	int cost;
} **A;

unsigned long n,m,*d,*pre,*Q,*pos,aux,*sel;

void citire()
{
	unsigned long x,y,i;
	int c;
	f>>n>>m;
	aux=n;
	sel=(unsigned long*)malloc((n+1)*sizeof(unsigned long));
	pos=(unsigned long*)malloc((n+1)*sizeof(unsigned long));
	Q=(unsigned long*)malloc((n+1)*sizeof(unsigned long));
	d=(unsigned long*)malloc((n+1)*sizeof(unsigned long));
	pre=(unsigned long*)malloc((n+1)*sizeof(unsigned long));
	A=(graf**)malloc((n+1)*sizeof(graf*));
	for(i=1;i<=n;i++)
	{
		A[i]=(graf*)malloc(sizeof(graf));
		A[i][0].cost=0;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		f>>c;
		A[x][0].cost++;
		A[x]=(graf*)realloc(A[x],(A[x][0].cost+1)*sizeof(graf));
		A[x][A[x][0].cost].y=y;
		A[x][A[x][0].cost].cost=c;
	}
	f.close();
}

void init(unsigned long start)
{
     unsigned long i;
     for(i=1;i<=n;i++)
     {
          pos[i]=i;
          Q[i]=i;
          d[i]=inf;
          pre[i]=start;
		  sel[i]=0;
     }
     pre[start]=0;
     d[start]=0;
     for(i=1;i<=A[start][0].cost;i++)
        d[A[start][i].y]=A[start][i].cost;
}

void combina(unsigned long i,unsigned long n)
{
    unsigned long tata=i,fiu=2*i,v=d[Q[i]],x=Q[i],p=pos[Q[fiu]];
    int ok=0;
    while(fiu<=n)
    {
        if(fiu<n)
            if(d[Q[fiu+1]]<d[Q[fiu]])
               ++fiu;
        if(v>d[Q[fiu]])
        {
            Q[tata]=Q[fiu];
			pos[Q[fiu]]=tata;
			tata=fiu;
			fiu*=2;
			if(ok)
				p*=2;
			ok=1;
        }
        else
           fiu=n+1;
    }
    Q[tata]=x;
    if(ok)
       pos[Q[tata]]=p;
}

void creareMinHeap()
{
    unsigned long i;
    for(i=n/2;i>=1;i--)
        combina(i,n);
}

void update_heap(unsigned long x) //deoarece cheia unui nod nu se poate mari ci doar micsora este suficient sa actualizez heap-ul doar in sus
{
	unsigned long fiu=pos[x],tata=fiu/2,aux,p;
	while(tata && d[Q[fiu]]<d[Q[tata]])
	{
		p=tata;
		aux=Q[tata];
		pos[Q[tata]]=fiu;
		Q[tata]=Q[fiu];
		pos[Q[fiu]]=p;
		Q[fiu]=aux;
		fiu=tata;
		tata=fiu/2;
	}
}

unsigned long extrageMin()
{
	unsigned long minim=Q[1];
	Q[1]=Q[n];
	pos[Q[n]]=1;
	--n;
	combina(1,n);
	return minim;
}

void dijkstra(int start)
{
	unsigned long i,x,j;
	x=extrageMin();
	sel[x]=1;
	for(i=1;i<=aux-1;i++)
	{
		x=extrageMin();
		sel[x]=1;
		for(j=1;j<=A[x][0].cost;j++)
			if(!sel[A[x][j].y])
				if(d[A[x][j].y]>d[x]+A[x][j].cost)
				{
					pre[A[x][j].y]=x;
					d[A[x][j].y]=d[x]+A[x][j].cost;
					update_heap(A[x][j].y);
				}
	}
}

void afisare()
{
	unsigned long i;
	for(i=2;i<=aux;i++)
		if(d[i]==inf)
			g<<"0 ";
		else
			g<<d[i]<<' ';
}

int main()
{

	citire();
	init(1);
	creareMinHeap();
	dijkstra(1);
	afisare();
    g.close();
	return 0;
}