#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define INFI 0x3f3f3f3f

using namespace std;

vector < pair <int,int> > g[50005];
queue <int> q;
int dist[50005],cnt[50005];
bool u[50005];

int main()
{
    int n,m,ok=0,x,y,c,i;
    vector < pair <int,int> >::iterator it;
    memset(dist,0x3f,sizeof(dist));
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=0;i<m;++i)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    dist[1]=0;
    q.push(1);
    while (!q.empty()&&!ok)
    {
        x=q.front();
        q.pop();
        u[x]=0;
        for (it=g[x].begin();it!=g[x].end();++it)
            if (dist[x]<INFI)
                if (dist[it->first]>dist[x]+it->second)
                {
                    dist[it->first]=dist[x]+it->second;
                    if (!u[it->first])
                    {
                        if (cnt[it->first]>n)
                            ok=1;
                        else
                        {
                            q.push(it->first);
                            u[it->first]=1;
                            ++cnt[it->first];
                        }
                    }
                }
    }
    if (!ok)
    {
        for (i=2;i<=n;++i)
            printf("%d ",dist[i]);
        printf("\n");
    }
    else
        printf("Ciclu negativ!\n");
    return 0;
}