#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;
    u=p=1;
    q[p]=x;
    up[x]=in[x]=1;
    while(p<=u)
    {
        a=q[p++];
        in[a]=0;
        if(d[a]<INF)
        {

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

                up[v[a][i].x]++;

                if(up[v[a][i].x]>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]);
}