#include <fstream>
#include <climits>
#include <queue>
#include <vector>
#define inf INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair <int, int> > graph[50001];
queue <int> q;
int viz[50001], nr[50001], i, x, y, n, m, d[50001], c;
int bell(int start){
    d[start] = 0;
    q.push(start);
    viz[start] = 1;
    while(!q.empty()){
        int node = q.front();
        viz[node] = 0;
        q.pop();
        for(int i = 0; i < graph[node].size(); i++){
            int new_node = graph[node][i].first;
            int cost = graph[node][i].second;
            if(d[new_node] > d[node] + cost){
                d[new_node] = d[node] + cost;
                nr[new_node]++;
                if(nr[new_node] > n - 1)
                    return -1;
                if(viz[new_node] == 0){
                    q.push(new_node);
                    viz[new_node] = 1;
                }
            }
        }
    }
    return 0;
}
int main()
{   f >> n >> m;
    for(i = 1; i <= m; i++){
        f >> x >> y >> c;
        graph[x].push_back({y,c});
    }
    for(i = 2; i <= n; i++)
        d[i] = inf;
    int ans = bell(1);
    if(ans == -1)
        g << "Ciclu negativ!";
    else{
        for(i = 2; i <= n; i++)
            g << d[i] << ' ';
    }
    return 0;
}