#include<cstdio>
#define INF 200000000
#include<vector>
#include<queue>
using namespace std;
struct da
{
    int x,p;
};
vector<da> v[50001];
queue<int>q;
int d[50001],n,m,ok,up[50001],in[50001];
void bellmanford(int x)
{
    d[x]=0;
    int u,p,i,a;
    //u=p=1;
    //q[p]=x;
    q.push(x);
    in[x]=1;
    //while(p<=u)
    while(!q.empty())
    {
        //a=q[p++];
        a=q.front();
        q.pop();
        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;
                    q.push(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]);
}