#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;
int N, M;
vector<int> dist, tata;

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

vector<edge> E;

void bellman_ford(int s){
    dist[s] = 0;
    bool relaxedAnEdge = true;
    for (int i = 1; i < N && relaxedAnEdge; ++i) {
        relaxedAnEdge = false;
        for (auto x : E){
            if(dist[x.to] > dist[x.from] + x.cost){
                dist[x.to] = dist[x.from] + x.cost;
                tata[x.to] = x.from;
                relaxedAnEdge = true;
            }
        }
    }
    for (int i = 1; i < N && !negative_cycle; ++i) {
        for (auto x : E){
            if(dist[x.to] > dist[x.from] + x.cost){
                negative_cycle = true;
                break;
            }
        }
    }
}

int main()
{
    in >> N >> M;
    dist.resize(N+1, inf);
    tata.resize(N+1, 0);
    E.resize(M);

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

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

    in.close();
    out.close();
    return 0;
}