#include<cstdio>
#define INF 200000000
#include<vector>
using namespace std;
struct da
{
    int x,p;
};
vector<da> v[50001];
int d[50001],n,m,ok,up[50001],q[50001],in[50001];

void bellmanford(int x)
{
    d[x]=0;
    ok=0;
    int u,p,i,a,z,w;

    u=p=1;
    q[p]=x;

    up[x]=in[x]=1;

    while(p<=u)
    {
        a=q[p++];
        in[a]=0;
        for(i=0; i<v[a].size(); i++)
        {
            z=v[a][i].x;
            w=v[a][i].p;
            if(d[z]>d[a]+w)
            {
                d[z]=d[a]+w;
                if(in[z]==0)
                {
                    q[++u]=z;
                    in[z]=1;
                }

                up[z]++;

                if(up[z]>n)
                {
                    ok=1;
                    break;
                }

            }
        }
        if(ok==1)break;

    }
}
int main()
{
    da p;
    int x,y,z,i;
    freopen("bellmanford.in","rt",stdin);
    freopen("bellmanford.out","wt",stdout);
    scanf("%ld%ld",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%ld%ld%ld",&x,&y,&z);
        p.x=y;
        p.p=z;
        v[x].push_back(p);
    }
    for(i=1; i<=n; i++)
        d[i]=INF;

    bellmanford(1);
    if(ok==1) printf("Ciclu negativ!");
    else
        for(i=2; i<=n; i++)
            printf("%ld ",d[i]);
}