#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
vector< pair<int, int> >v[50005];
queue <int> q;
int dist[50005];
int viz[50005];
int inqueue[50005];
int oo=2000000009;
int x,y,c;

bool bellmanford (int nodstart) {

    for (int i=1;i<=n;i++) {
        viz[i] = 0;
        inqueue[i] = 0;
        dist[i] = oo;
    }
    dist[nodstart] = 0;
    q.push(nodstart);
    inqueue[nodstart] = 1;

    while (q.empty()==0) {
        int nod = q.front();
        viz[nod]++;
        if (viz[nod] >= n) {
            return 0;
        }
        q.pop();
        inqueue[nod] = 0;
        for (int i=0;i<v[nod].size();i++) {
            int nodtoviz = v[nod][i].first;
            int distance = v[nod][i].second;
            if (dist[nodtoviz] > dist[nod] + distance) {
                dist[nodtoviz] = dist[nod] + distance;
                if (inqueue[nodtoviz]==0)
                    q.push(nodtoviz);
            }
        }
    }

    return 1;
}

int main() {
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> x >> y >> c;
        v[x].push_back(make_pair(y,c));
    }
      if (bellmanford(1)!=0)  {
            for (int i=2;i<=n;i++)
                g << dist[i] << " ";
        }
        else {
            g << "Ciclu negativ!";
        }

    return 0;
}