#include <stdio.h>
#include <stdlib.h>
#define nmax 50000
#define inf 0x3f3f3f3f
using namespace std;
FILE *fin,*fout;
int n,m,H_size=0,dist[nmax+5];
struct nod
{
    int info,dist;
    nod *urm;
}*v[nmax+5],*c,*d;
struct heap
{
    int info,dist;
}H[nmax+5];
inline int tata(int k)
{
    return k>>1;
}
inline int fius(int k)
{
    return k<<1;
}
inline int fiud(int k)
{
    return k<<1+1;
}
void percolate(int k)
{
    heap key=H[k];
    while(k>1 && k<=H_size && H[tata(k)].dist>H[k].dist)
    {
        H[k]=H[tata(k)];
        H[tata(k)]=key;
        key=H[tata(k)];
        k=tata(k);
    }
}
void sift(int k)
{
    int son;
    heap key;
    do
    {
        son=0;
        key=H[k];
        if(fius(k)>1 && fius(k)<=H_size)
            if(fiud(k)>1 && fiud(k)<=H_size)
                if(H[fiud(k)].dist<H[fius(k)].dist)
                son=fiud(k);
                else
                son=fius(k);
            else
                son=fius(k);
        else
            son=0;
        if(H[son].dist<H[k].dist)
        {
            H[k]=H[son];
            H[son]=key;
            k=son;
        }
        else
            son=0;
    }while(son && k>=1 && k<H_size);
}
void adauga(int x,int z)
{
    H_size++;
    H[H_size].info=x;
    H[H_size].dist=z;
    percolate(H_size);
}
void sterge(int k)
{
    H[k]=H[H_size];
    H_size--;
    if(H[k].dist<H[tata(k)].dist)
        percolate(k);
    else
        sift(k);
}
void heapify()
{
    for(int i=H_size/2;i>0;--i)
        sift(i);
}
int main()
{
    int x,y,z;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->dist=0;
        v[i]->urm=0;
        dist[i]=inf;
        H[i].dist=inf;
        H[i].info=-1;
    }
    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d %d",&x,&y,&z);
        c=v[x];
        while(c->urm)
            c=c->urm;
        d=new nod;
        d->info=y;
        d->dist=z;
        d->urm=0;
        c->urm=d;
    }
    dist[1]=0;
    adauga(1,0);
    while(H_size)
    {
        x=H[1].info;
        z=H[1].dist;
        sterge(1);
        c=v[x];
        while(c->urm)
        {
            c=c->urm;
            if(dist[c->info]>c->dist+z)
            {
                adauga(c->info,c->dist+z);
                dist[c->info]=c->dist+z;
            }
        }
        heapify();
    }
    for(int i=2;i<n;i++)
        if(dist[i]==inf)
        fprintf(fout,"%d ",0);
        else
        fprintf(fout,"%d ",dist[i]);
    if(dist[n]!=inf)
    fprintf(fout,"%d",dist[n]);
    else
    fprintf(fout,"%d",0);
    return 0;
}