#include <cstdio>
#include <string.h>
#define oo 0x3f3f3f3f
#define DIM 8192

char ax[DIM];
int pz;

inline void cit(int &x)
{
    x=0;
    int semn = 1;
    while(ax[pz]< '0' || ax[pz] > '9')
        if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
    if(ax[pz-1] == '-')
        semn = -1;
    while(ax[pz]>='0' && ax[pz]<='9')
    {
        x=x*10+ax[pz]-'0';
        if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
    }
    x*=semn;
}

struct nod { int x, y, c;};

nod a[250001];
int d[50001];
int n, m;

void read()
{
    freopen("bellmanford.in","r",stdin);
    cit(n);cit(m);
    for(int i=1;i<=m;++i) cit(a[i].x), cit(a[i].y), cit(a[i].c);

}

void bell()
{
    int ok=1,i;
    int p,q,c;
    memset(d, oo, sizeof(d));
    d[1]=0;

    while(ok)
    {
        ok=0;
        for(i=1;i<=m;++i)
        {
            p=a[i].x, q=a[i].y, c=a[i].c;
            if(d[p] + c < d[q]) d[q]=d[p]+c, ok=1;
        }
    }

    for(i=2;i<=n;++i)
        if(d[i]==oo) printf("0 ");
                else printf("%d ", d[i]);


}

int main()
{
    freopen("bellmanford.out","w",stdout);
    read();
    bell();
    return 0;
}