#include <fstream>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct vecin{
    int next;
    int cost;
};

struct stare{
    int curr;
    int total;
};

int n, m;
int dist[50005];
int cnt_coada[50005];
bool in_q[50005];
vector<vecin> v[50005];
queue<int> q;

int bellman(){
    q.push(1);
    while (!q.empty()){
        int curr = q.front();
        q.pop();
        if (cnt_coada[curr] >= n)
            return 0;
        in_q[curr] = 0;
        for (auto[vecin, cost]: v[curr]){
            if (dist[curr] + cost < dist[vecin]){
                dist[vecin] = dist[curr] + cost;
                if (!in_q[vecin]){
                    in_q[vecin] = 1;
                    q.push(vecin);
                    cnt_coada[vecin]++;
                }
            }
        }
    }
    return 1;
}
int main(){
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int sursa, vec, cost;
        fin >> sursa >> vec >> cost;
        v[sursa].push_back({vec, cost});
    }

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