#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int oo = 0x3f3f3f3f;

class Graph {
  public:
    class Edge {
      public:
        Edge(const int _from, const int _to, const int _cost):
          from(_from),
          to(_to),
          cost(_cost) {}

        int From() const {
            return from;
        }

        int To() const {
            return to;
        }

        int Cost() const {
            return cost;
        }

      private:
        int from, to, cost;
    };

    Graph(const int _v = 0):
      v(_v),
      edges(vector< vector<Edge> >(v, vector<Edge>())) {}

    int V() const {
        return v;
    }

    vector<Edge>::const_iterator EdgesBegin(const int x) const {
        return edges[x].begin();
    }

    vector<Edge>::const_iterator EdgesEnd(const int x) const {
        return edges[x].end();
    }

    void AddEdge(const Edge &e) {
        edges[e.From()].push_back(e);
    }

  private:
    int v;
    vector< vector<Edge> > edges;
};

bool BellmanFord(const Graph &graph, const int source, vector<int> &distances) {
    distances = vector<int>(graph.V(), oo);
    queue<int> q;
    vector<bool> inQ = vector<bool>(graph.V(), false);
    vector<int> timesRelaxed = vector<int>(graph.V(), 0);
    distances[source] = 0;
    q.push(source);
    inQ[source] = true;
    for (; !q.empty(); q.pop()) {
        int x = q.front();
        inQ[x] = false;
        if (timesRelaxed[x] > graph.V())
            return true;
        for (vector<Graph::Edge>::const_iterator e = graph.EdgesBegin(x); e != graph.EdgesEnd(x); ++e) {
            if (distances[x] + e->Cost() < distances[e->To()]) {
                distances[e->To()] = distances[x] + e->Cost();
                if (!inQ[e->To()]) {
                    q.push(e->To());
                    inQ[e->To()] = true;
                    ++timesRelaxed[e->To()];
                }
            }
        }
    }
    return false;
}

Graph G;
vector<int> Distances;
bool NegativeCycle;

void Solve() {
    NegativeCycle = BellmanFord(G, 0, Distances);
}

void Read() {
    ifstream cin("bellmanford.in");
    int v, e;
    cin >> v >> e;
    G = Graph(v);
    for (; e > 0; --e) {
        int from, to, cost;
        cin >> from >> to >> cost;
        G.AddEdge(Graph::Edge(--from, --to, cost));
    }
    cin.close();
}

void Print() {
    ofstream cout("bellmanford.out");
    if (NegativeCycle) {
        cout << "Ciclu negativ!\n";
    } else {
        for (int x = 1; x < G.V(); ++x)
            cout << Distances[x] << " ";
        cout << "\n";
    }
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}