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

int e,n,m,d[50001][2];

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]=0;
    ++n;
    for(int i=2;i<n;++i)
    {
        d[i][0]=inf;
    }
    graf *nod=a[1];
    if(nod) e=1;
    else e=0;
    while(nod)
    {
        d[nod->v][0]=nod->c;
        d[nod->v][1]=1;
        nod=nod->u;
    }
}

void bellmanford()
{
    int i;
    graf* nod;
    for(int k=2;k<n&&e;++k)
    {
        e=0;
        for(i=2;i<n;++i)
        {
            if(d[i][1])
            {
                d[i][1]=0;
                nod=a[i];
                while(nod)
                {
                    if(d[nod->v][0]>d[i][0]+nod->c)
                    {
                        e=1;
                        d[nod->v][1]=1;
                        d[nod->v][0]=d[i][0]+nod->c;
                    }
                    nod=nod->u;
                }
            }
        }
    }
}

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

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

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