#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;
    int u,p,i,a;
    u=p=1;
    q[p]=x;
    in[x]=1;
    while(p<=u)
    {
        a=q[p++];
        in[a]=0;
        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]);
}