#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
#define inf 0x7fffffff
using namespace std;

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

bool negative_cycle = false;
int N, M;
vector<int> dist, tata;

struct edge{
    int from;
    int to;
    int cost;
};

vector<struct edge> E;

void bellman_ford(int s){
    dist.resize(N+1, inf);
    tata.resize(N+1, 0);
    dist[s] = 0;

    for (int i = 0; i < N-1; ++i) {
        for (struct edge edge : E)
            if (dist[edge.from] + edge.cost < dist[edge.to])
                dist[edge.to] = dist[edge.from] + edge.cost;
    }

    for (int i = 0; i < N-1; ++i) {
        for (struct edge edge : E)
            if (dist[edge.from] + edge.cost < dist[edge.to])
                negative_cycle = 1;
    }
}

int main()
{
    in >> N >> M;
    E.resize(M);
    for (int i = 0; i < M; ++i) {
        in >> E[i].from >> E[i].to >> E[i].cost;
    }
    in.close();
    
    bellman_ford(1);

    if(negative_cycle)
        out << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; ++i){
            out << dist[i] << ' ';
        }
    out.close();
    return 0;
}