#include <algorithm>
    #include <vector>
    #include <unordered_map>
    #include <functional>
    #include <climits>
    #include <iostream>
    #define ATCODER
     
    class edge {
    public:
        edge(int to, long long cost);
        int get_to() const;
        long long get_cost() const;
    private:
        int to;
        long long cost;
    };
     
    edge::edge(int to, long long cost) : to(to), cost(cost) {}
     
    int edge::get_to() const { return to; }
     
    long long edge::get_cost() const { return cost; }
     
     
    class bellman_ford {
    private:
        //unordered_mapを使って隣接グラフを構築
        //first:接続元、second:辺のコストと接続先
        std::unordered_map<int, std::vector<edge>> adj_list;
        int node_num;
        int start_point;
        std::vector<int> pred;//経路（遷移元）を保持
        std::vector<long long> costs;//距離を保持
        bool is_negative_graph;//グラフ内に負のサイクルをもつか否か
        std::vector<bool> is_negative_pass;//経路上に負のサイクルを持つか否か
     
    public:
        bellman_ford(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list);
        void calc_min_cost(int start);
        long long get_cost(int end) const;
        bool get_is_negative_graph() const;
        std::vector<int> get_min_path(int end) const;
    };
     
    bellman_ford::bellman_ford(const int node_num, 
                                const std::unordered_map<int, std::vector<edge>>& adj_list) :
        adj_list(adj_list),
        start_point(0),
        node_num(node_num),
        pred(node_num + 1, INT_MAX),
        costs(node_num + 1, LLONG_MAX),
        is_negative_graph(false),
        is_negative_pass(node_num + 1, false)
    {}
     
    void bellman_ford::calc_min_cost(int start) {
        this->start_point = start;
        this->pred = std::vector<int>(node_num + 1, INT_MAX);
        this->costs = std::vector<long long>(node_num + 1, LLONG_MAX);
        this->is_negative_pass = std::vector<bool>(node_num + 1, false);
     
        pred[start] = -1;
        costs[start] = 0;
        for (int i = 0; i < 2 * node_num; i++) {
            for (auto &node : adj_list) {
                if (costs[node.first] == LLONG_MAX) continue;
                for (auto &adj : adj_list[node.first]) {
                    int adj_node = adj.get_to();
                    long long adj_cost = adj.get_cost() + costs[node.first];
                    if (adj_cost < costs[adj_node]) {//計算された隣接頂点のコストが現在のコストより小さいなら
                        costs[adj_node] = adj_cost;//隣接頂点のコストを更新
                        pred[adj_node] = node.first;//隣接頂点の遷移元を更新
                        if (i >= node_num - 1) {
                            //頂点数回以上繰り返しても、
                            //まだ更新が発生するなら、その頂点への経路には負のサイクルあり
                            is_negative_pass[adj_node] = true;
                            is_negative_graph = true;
                        }
                    }
                    if (is_negative_pass[node.first] == true) {//負のサイクル情報伝搬
                        //経路に負のサイクルを含む頂点に連結されているなら、
                        //その頂点への経路も負のサイクルを含む
                        is_negative_pass[adj_node] = true;
                    }
                }
            }
        }
    }
     
    bool bellman_ford::get_is_negative_graph() const{
        return is_negative_graph;
    }
     
    long long bellman_ford::get_cost(int end) const {
        if (is_negative_pass[end] == false)
            return costs[end];
        else
            return LLONG_MIN;
    }
     
    std::vector<int> bellman_ford::get_min_path(int end) const {
        int node = end;
        std::vector<int> vec;
        vec.push_back(node);
        //終点から始点までの経路をたどる
        while (1) {
            //負のサイクルを含む頂点or
            //始点から辿れない頂点or
            //始点であれば終了
            if (is_negative_pass[node] == true ||
                pred[node] >= INT_MAX || pred[node] == -1) break;
            node = pred[node];
            vec.push_back(node);
        }
        std::reverse(vec.begin(), vec.end());
        return vec;
    }
     
    int main()
    {
    #ifndef ATCODER
        std::unordered_map<int, std::vector<edge>> adj_list;
        int node_num, edge_num, r;
        std::cin >> node_num;
        std::cin >> edge_num;
        std::cin >> r;
        for (int i = 0; i < edge_num; i++) {
            int s, t;
            long long d;
            std::cin >> s;
            std::cin >> t;
            std::cin >> d;
            adj_list[s].push_back(edge(t, d));
        }
     
        bellman_ford bell(node_num, adj_list);
        bell.calc_min_cost(r);
        if (bell.get_is_negative_graph() == false) {
            for (int i = 0; i <= node_num; i++) {
                long long cost = bell.get_cost(i);
                if (cost == LLONG_MAX)
                    std::cout << "INF\n";
                else
                    std::cout << cost << '\n';
                std::vector<int> path = bell.get_min_path(i);
            }
        }
        else {
            std::cout << "NEGATIVE CYCLE\n";
        }
    #else
        std::unordered_map<int, std::vector<edge>> adj_list;
        int N, M;
        std::cin >> N;
        std::cin >> M;
        for (int i = 0; i < M; i++) {
            int a, b;
            long long c;
            std::cin >> a;
            std::cin >> b;
            std::cin >> c;
            adj_list[a].push_back(edge(b, -c));
        }
     
        bellman_ford bell(N, adj_list);
        bell.calc_min_cost(1);
        long long cost = bell.get_cost(N);
        if (cost == LLONG_MIN) {
            std::cout << "inf\n";
        }
        else {
            std::cout << -cost << "\n";
        }
     
    #endif
     
    }

Measured memory_bytes: 512