#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define N_MAX 50005
using namespace std;
using PI = pair<int, int>;

ifstream in { "bellmanford.in" };
ofstream out { "bellmanford.out" };

int n;
vector<PI> muchii[N_MAX];
int been_in_queue[N_MAX];
bool is_in_queue[N_MAX];
int d[N_MAX];

bool Bellman_Ford() {
    d[1] = 0;
    
    queue<int> q;
    q.push(1);
    
    while (!q.empty()) {
        int current = q.front();
        if (++been_in_queue[current] >= n)
            return false;
        
        q.pop();
        is_in_queue[current] = false;
        
        for (auto& p : muchii[current])
            if (d[p.first] > d[current] + p.second) {
                d[p.first] = d[current] + p.second;
                
                if (!is_in_queue[p.first]) {
                    is_in_queue[p.first] = true;
                    q.push(p.first);
                }
            }
    }
    
    return true;
}

int main() {
    int m;
    in >> n >> m;
    
    while (m--) {
        int x, y, c;
        in >> x >> y >> c;
        muchii[x].push_back({ y, c });
    }
    
    memset(d, 0x3f, sizeof(int) * (n + 5));
    
    if (Bellman_Ford()) {
        for (int i { 2 }; i <= n; ++i)
            out << d[i] << ' ';
    } else {
        out << "Ciclu negativ!";
    }
}