#include <cstdio>
using namespace std;
const int inf=9<<30;

int k,n,m,ciclunegativ=0,d[50001],inlista[50001];
unsigned short nrintrariinlista[50001],lista[250001];

struct graf
{
    int v,c;
    graf* u;
}*a[50001];

void read()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x;
    graf *nod;
    for(int i=0;i<m;++i)
    {
        scanf("%d",&x);
        nod=new graf;
        nod->u=a[x];
        a[x]=nod;
        scanf("%d",&x);
        nod->v=x;
        scanf("%d",&x);
        nod->c=x;
    }
}

void init()
{
    d[1]=0;
    ++n;
    for(int i=2;i<n;++i)
    {
        d[i]=inf;
    }
    graf *nod=a[1];
    k=0;
    while(nod)
    {
        d[nod->v]=nod->c;
        lista[k++]=nod->v;
        inlista[nod->v]=1;
        ++nrintrariinlista[nod->v];
        nod=nod->u;
    }
}

void bellmanford()
{
    int i;
    graf* nod;
    for(int k1=0;k1<k;++k1)
    {
        i=lista[k1];
        inlista[i]=0;
        nod=a[i];
        while(nod)
        {
            if(d[nod->v]>d[i]+nod->c)
            {
                d[nod->v]=d[i]+nod->c;
                if(!inlista[nod->v])
                {
                    if(++nrintrariinlista[nod->v]>n-1)
                    {
                        ciclunegativ=1;
                        return;
                    }
                    lista[k++]=nod->v;
                    inlista[nod->v]=1;
                }
            }
            nod=nod->u;
        }
    }
}

int negative()
{
    graf *nod;
    for(int i=1;i<n;++i)
    {
        nod=a[i];
        while(nod)
        {
            if(d[i]+nod->c<d[nod->v]) return 1;
            nod=nod->u;
        }
    }
    return 0;
}

void scrie()
{
    freopen("bellmanford.out","w",stdout);
    if(ciclunegativ) printf("Ciclu negativ!");
    else for(int i=2;i<n;++i) printf("%d ",d[i]);
    printf("\n");
}

int main()
{
    read();
    init();
    bellmanford();
    scrie();
    return 0;
}