#include <cstdio>
using namespace std;
struct graf
{
    unsigned short x;
    int l;
    graf *u;
};
graf *g[50001];
int d[50001];
//unsigned short unde[50001];
void bag(unsigned short a,unsigned short b,int l)
{
    graf *q = new graf;
    q->x=b;
    q->l=l;
    q->u=g[a];
    g[a]=q;
}
int main()
{

    unsigned short n,a,b,poz;
    short l;
    int m,i,cmin;
    graf *p,*q;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%hu%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%hu%hu%hd",&a,&b,&l);
        if(a==1) d[b]=l;
         bag(a,b,l);
    }
    for(i=1;i<=n;++i)
    if(d[i]==0) d[i]=50000001;
    while(g[1]!=NULL)
    {
        cmin=g[1]->l;
        q=g[1];
        while(q->u!=NULL)
        {
            if(q->u->l<cmin)
            {
                cmin=q->u->l;
                p=q;
            }
            q=q->u;
        }
        if(cmin!=g[1]->l)
        {
            poz=p->u->x;
            p->u=p->u->u;
        }
        else
        {
            poz=g[1]->x;
            g[1]=g[1]->u;
        }
            q=g[poz];
            while(q!=NULL)
            {

                if(d[q->x]==50000001)
                {
                    d[q->x]=cmin+q->l;
                    //unde[q->x]=poz;
                    bag(1,q->x,d[q->x]);
                }
                else if (d[q->x]>cmin+q->l)
                {
                   // if(unde[q->x]==poz) {
                      //  printf("Ciclu negativ!\n");
                      //  return 0;
                        //       }
                    //unde[q->x]=poz;
                    d[q->x]=cmin+q->l;
                    p=g[1];
                    while(p->x!=q->x)
                    {
                        p=p->u;
                        if(p==NULL)
                        {
                         printf("Ciclu negativ!\n");
                        return 0;
                        }
                    }
                    p->l=cmin+q->l;
                }
                q=q->u;
            }

    }
    for(i=2;i<n;++i)
    printf("%d ",d[i]);
    printf("%d\n",d[n]);
    return 0;
}