#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[s] = 0;
    for (int i = 1; i <= N; ++i) {
        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;
            }
        }
    }

    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)
        out << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; ++i){
            out << dist[i] << ' ';
        }

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