#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax=5e4+10,mmax=25e4+10,inf=0x3f3f3f3f;

 queue <int> Q;
 vector< pair<int,int> > adj[nmax];
 int dist[nmax],counter[nmax];
 bitset<nmax> inQueue;
 int n,m;

 void read()
 {
     fin>>n>>m;
     for(int i=0;i<m;i++)
     {
         int x,y,c;
         adj[x].push_back({y,c});
     }
 }

 bool BellmanFord()
 {
     fill(dist+1,dist+n+1,inf);
     dist[1]=0;
     counter[1]=1;

     Q.push(1);

     while(!Q.empty())
     {
         int x=Q.front(),y,c;
         Q.pop();

         inQueue[x]=false;

         for(auto it: adj[x])
         {
             y=it.first,c=it.second;

             if(dist[y]>dist[x]+c)
             {
                 dist[y]=dist[x]+c;

                 if(!inQueue[y])
                 {
                     inQueue[y]=true;
                     q.push(y);

                     counter[y]++;
                     if(counter[y]>=n)
                        return false;
                 }
             }
         }
     }
     return true;
 }

int main()
{
    read();
    if(!BellmanFord())
        fout<<"Ciclu negativ!";
    else
        for(int i=1;i<=n;i++)
            fout<<dist[i]<<" ";
    return 0;
}