#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;


#define to first
#define cost second
#define pb push_back
#define mp make_pair
#define nmax 50010

int app[nmax], dist[nmax], N, M, X, Y, C;
vector<pair<int, int> > G[nmax];
bool InQueue[nmax];

int BellmanFord()
{
     int i, node;
     for(i = 1; i <= N; i++) dist[i] = 0x3f3f3f3f;
     dist[1] = 0;
     queue<int> Q;
     Q.push(1);
     app[1] = 1;
     InQueue[1] = true;
     while(!Q.empty())
     {
             vector<pair<int, int> > :: iterator it;
             node = Q.front();
             Q.pop();
             InQueue[node] = false;
             if(app[node] > N) return 1;
             for(it = G[node].begin(); it != G[node].end(); ++it)
                    if(dist[it -> to] > dist[node] + it -> cost)
                    {
                               dist[it -> to] = dist[node] + it -> cost;
                               if(!InQueue[it -> to])
                               {
                                              InQueue[it -> to] = true;
                                              app[it -> to] ++;
                                              Q.push(it -> to);
                               }
                    }
     }
     return 0;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i %i", &X, &Y, &C);
          G[X].pb(mp(Y, C));
    }
    if(BellmanFord()) printf("Ciclu negativ!\n");
    else for(i = 2; i <= N; i++) printf("%i ", dist[i]);
    return 0;
}