#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#define nmax 50005
#define inf (1<<30)
using namespace std;

void get_data (int &n, int &m, vector < pair<int, int> > v[nmax]){
    int x, y, w;
    ifstream fin ("bellmanford.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        fin >> x >> y >> w;
        v[x]. push_back (make_pair(y, w));
    }
}

void solve (int n, int m, int dist[], vector < pair<int, int> > v[nmax], bool &ciclu){
    queue <int> q;
    int cycle[nmax];
    for (int i = 1; i <= n; i++)
        cycle[i] = 0;
    for (int i = 2; i <= n; i++)
        dist[i] = inf;
    dist[1] = 0;
    q.push (1);
    while (!q.empty()){
        int current = q.front();
        q.pop();
        cycle[current]++;
        if (cycle[current] >= n-1){
            ciclu = true;
            return;
        }
        for (auto x : v[current])
            if (dist[x.first] > dist[current] + x.second){
                dist[x.first] = dist[current] + x.second;
                q.push(x.first);
            }
    }
    ciclu = false;
}

void print_data (int n, int dist[], bool ciclu){
    ofstream fout ("bellmanford.out");
    if (!ciclu)
        for (int i = 2; i <= n; i++)
            if (dist[i] == inf)
                fout << 0 << " ";
        else
            fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";
}

int main(){
    int n, m;
    int dist[nmax];
    bool ciclu;
    vector < pair<int, int> > v[nmax];
    get_data (n, m, v);
    solve (n, m, dist, v, ciclu);
    print_data (n, dist, ciclu);
    return 0;
}