#include <cstdio>
#include <deque>
#include <climits>
#include <vector>
#define pb push_back
#define pf pop_front
#define sz size
#define NMAX 50001
#define INF INT_MAX

using namespace std;

FILE *f = freopen("bellmanford.in", "r", stdin);
FILE *g = freopen("bellmanford.out", "w", stdout);

class node{
public:
    int y, cost;
    node(int y, int cost) {
        this -> y = y;
        this -> cost = cost;
    }
};

vector <node> G[NMAX];
deque <int> Q;
bool in_queue[NMAX], negative = false;
int n = 0, m = 0, dist[NMAX];

void read_data(int &n, int &m) {
    scanf("%d%d", &n, &m);
    for(int i = 1; i<=m; i++) {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        G[x].pb(node(y, cost));
    }
}


void bellman(int n, int start, deque <int> Q, vector<node> G[NMAX], int dist[]) {
    for(int i =1 ; i<=n; i++) {
        dist[i] = INF;
    }
    Q.pb(start);
    vector<node> ::iterator it;
    in_queue[start] = true;
    dist[start] = 0;
    while(!Q.empty()) {
        int node = Q.front();
        Q.pf();

        for(it = G[node].begin(); it != G[node].end(); it++) {
            if(dist[node] + it->cost < dist[it->y]) {
                dist[it->y] = dist[node] + it->cost;
                if(!in_queue[it->y]) {
                    Q.pb(it->y);
                    in_queue[it->y] = true;
                }
            }
        }
    }
}

bool check_negative(vector <node> G[], int n, int dist[]) {

    vector <node> ::iterator it;
    for(int i =1 ; i<=n; i++) {
        for(it = G[i].begin(); it != G[i].end(); it++) {
            if(dist[i] + it->cost < dist[it->y]) {
                return true;
            }
        }
    }
    return false;
}


int main() {
    read_data(n, m);
    bellman(n, 1, Q, G, dist);
    negative = check_negative(G, n, dist);
    if(negative == true) {
        printf("Ciclu negativ!\n");
    }
    else {
        for(int i = 2; i<=n; i++) {
            printf("%d ", (dist[i] < INF ? dist[i]:0));
        }

    }

    return 0;
}