# include <cstdio>
# include <math.h>
# include <vector>

using namespace std;

# define FIN "bellmanford.in"
# define FOUT "bellmanford.out"
# define MAX_N 50005
# define MAX_E 1000
# define INF 0x3f3f3f3f

int N, M, i, Vf;
int CNT[MAX_N];
int DIST[MAX_N];
int Queue[MAX_N];
vector <pair<int, int> > G[MAX_N];

     bool bellman(int start_node)
     {
         memset(DIST, INF, sizeof(DIST));
         CNT[start_node] = 1;
         DIST[start_node] = 0; Queue[Vf = 0] = start_node;
         
         int cur_node;
         for (int i = 0; i <= Vf; ++i)
         {
             cur_node = Queue[i % (N + 1)];
             CNT[cur_node] *= (-1);
             
             vector <pair <int, int> > :: iterator it;
             for (it = G[cur_node].begin(); it != G[cur_node].end(); ++it)
                if (DIST[cur_node] + it -> second < DIST[it -> first])
                {
                     DIST[it -> first] = DIST[cur_node] + it -> second;
                     if (CNT[it -> first] <= 0)
                     {
                          CNT[it -> first] = 1 - CNT[it -> first];
                          Queue[(++Vf) % (N + 1)] = it -> first;
                     }
                     if (CNT[it -> first] > N || (DIST[it -> first] < INF && abs(DIST[it -> first]) > M * MAX_E)) return true;
                }
         }
         
         return false;
     }

     int main()
     {
         freopen(FIN, "r", stdin);
         freopen(FOUT, "w", stdout);
         
         scanf("%d%d", &N, &M);
         
         int x, y, c;
         for (i = 1; i <= M; ++i)
         {
             scanf("%d%d%d", &x, &y, &c);
             
             G[x].push_back(make_pair(y, c));
         }
         
         if (bellman(1) == true) printf("Ciclu negativ!");
         else
            for (i = 2; i <= N; ++i) printf("%d ", DIST[i]);
         
         return 0;
     }