#include<fstream>
#include<vector>
#include<queue>

const int N_MAX = 5005;
const int INF = 1e9;

std :: vector <std :: pair<int, int> > graph[N_MAX];
int dist[N_MAX], nr[N_MAX], n, m;
bool used[N_MAX], cycle;
std :: queue <int> q;


int main() {
    std :: ifstream fin("bellmanford.in");
    std :: ofstream fout("bellmanford.out");

    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }

    int node;
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    q.push(1);
    used[1] = true;
    cycle = false;
    while(!q.empty() && !cycle) {
        node = q.front();
        used[node] = false;
        q.pop();
        for(auto i : graph[node]) {
            if(dist[i.first] > dist[node] + i.second) {
                dist[i.first] = dist[node] + i.second;
                if(!used[i.first]) {
                    q.push(i.first);
                    used[i.first] = true;
                    if(++nr[i.first] > n)
                        cycle = true;
                }
            }
        }
    }

    if(cycle)
        fout << "Ciclu negativ!\n";
    else {
        for(int i = 2; i <= n; i++)
            fout << dist[i] << " ";
        fout << "\n";
    }
    return 0;
}