#include <cstdio>
#define MAXN 50001
#define FOR(i,a,b) for(i=a;i<=b;i++)
#define inf 1<<30

struct graf
{
  int nod,cost;
  graf *next;
};


graf *a[MAXN];
int h[MAXN],poz[MAXN],d[MAXN];
int n,m,k;

void read()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int x,y,z,i;
    scanf("%d %d",&n,&m);
    FOR(i,1,m)
    {
        scanf("%d %d %d",&x,&y,&z);
        graf *q=new graf;
        q->nod=y;
        q->cost=z;
        q->next=a[x];
        a[x]=q;
    }
}

void swap(int a,int b)
{
    int aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

void upheap(int i)
{
    while(i>1 && d[h[i/2]]>d[h[i]])
    {
        poz[h[i/2]]=i;
        poz[h[i]]=i/2;
        swap(i,i/2);
        i=i/2;
    }
}

void downheap(int i)
{
    int stg,dr,max=i;
    stg=2*i;
    dr=2*i+1;
    if(stg<=k && d[h[stg]]<d[h[i]])
        max=stg;
    if(dr<=k && d[h[dr]]<d[h[max]])
        max=dr;
    if(max!=i)
    {
        poz[h[max]]=i;
        poz[h[i]]=max;
        swap(max,i);
        downheap(max);
    }
}


void dijkstra_heap()
{
	int i;
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		poz[i]=-1;
	}
	d[1]=0;
	h[1]=1;
	poz[1]=1;
	k++;
	while(k)
	{
		int min=h[1];
		swap(1,k);
		poz[h[1]]=1;
		k--;
		downheap(1);
		graf *q=a[min];
		while(q)
		{
			if(d[q->nod]>d[min]+q->cost)
			{
				d[q->nod]=d[min]+q->cost;
				if(poz[q->nod]!=-1)
					upheap(poz[q->nod]);
				else
				{
					h[++k]=q->nod;
					poz[h[k]]=k;
					upheap(k);
				}
			}
			q=q->next;
		}
	}
}

void print()
{
    int i;
    FOR(i,2,n)
    {
        if(d[i]==inf)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }
    printf("\n");
}

int main()
{
    read();
    dijkstra_heap();
    print();
    return 0;
}