#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int, int>> a[50001];
int n, m;
int d[50001];
int ciclu = 0;

const int Inf = 1e9;

void read() {
    int i, x, y, cost;
    ifstream f("bellmanford.in");
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> cost;
        a[x].emplace_back(y, cost);
    }
    f.close();
}

int cnt[50001];
bool viz[50001];

queue<int> Q;
void bellmanford(int x) {
    int i;
    viz[x] = 1;
    d[x] = 0;
    Q.push({x});
    while (!Q.empty() && !ciclu) {
        x = Q.front();
        Q.pop();
        viz[x] = 0;
        for (i = 0; i < a[x].size(); i++)
            if (d[x] < Inf)
                if (d[x] + a[x][i].second < d[a[x][i].first]) {
                    d[a[x][i].first] = d[x] + a[x][i].second;
                    if (!viz[a[x][i].first]) 
                        if (cnt[a[x][i].first] > n) 
                            ciclu = 1;
                        else {
                            viz[a[x][i].first] = 1;
                            cnt[a[x][i].first]++;
                            Q.push(a[x][i].first);
                        }
                }
            }
}

void output() {
    ofstream g("bellmanford.out");
    if (ciclu)
        g << "Ciclu negativ!";
    else {
        int i;
        for (i = 2; i <= n; i++)
            g << d[i] << ' ';
    }
    g.close();
}

int main() {
    read();
    int i;
    for (i = 1; i <= n; i++)
        d[i] = Inf;
    bellmanford(1);
    output();
    return 0;
}