/**
 * @brief  ??????????????????(shortest paths problem)????????????Bellman-Ford??¢?????´?????????(Bellman-Ford algorithm)?????±???
 * @note   ??¢??£URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B
 * @date   2016/02/18~2017/01/03
 */



//****************************************
// ???????????????????????????????????????????????????
//****************************************

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <tuple>
#include <functional>



//****************************************
// ???????????§????????¢?????????????????????
//****************************************

#define GRAPH_BEGIN namespace graph {
#define GRAPH_END   }



//****************************************
// ????????????????§????
//****************************************

GRAPH_BEGIN



//****************************************
// ?§????????????????
//****************************************

using weight_t   = std::int32_t;  /**< ???(u, v)????????????w?????¨?????? */
using index_t    = std::int32_t;  /**< ??????v??????????????¨??????       */
using capacity_t = weight_t;      /**< ???(u, v)??????????????¨??????    */



namespace limits {
    enum {  // scoped??§????????????????????????????????????enum(strongly-typed enum)??§?????????
        inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief ???????????¨???????????´???????????¨????????????     */
        nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief ?????????????????¨???????????´???????????¨???????????? */
    };
}



/**
 * @brief  ????????????????§???????(scoped enum)
 * @detail (u, v) ??? E??§??????u??????????????°??????v?????°????????§??????
 *         ?????????????????????????????£??\????????¨?????????????????????????????§??????
 *         ??°???????????????????????£??\???????????¨???????????????????????????????????¢??????????????¨???????????????????¢?????????????
 */
enum struct vcolor : std::int32_t {
    white,  /**< ??????????????? */
    black,  /**< ??¢???????????? */
    gray,   /**< ??¢???????????? */
};

/**
 * @brief ??°????????¨?????????(??????) 
 */
struct vertex {
    union {
        weight_t d;       /**< ?§????s??????????????¢  */
        weight_t key;     /**< Prim?????¢?????´???????????????????????¨????±?????????????????????¨????????¶?????? */
    };
    index_t pi;           /**< ????????????(?????????) */
    union {
        vcolor color;     /**< ????????????        */
        bool  visited;    /**< ????????????????     */
    };
    // weight_t f;           /**< ??????????????°(DFS?????????????????????????????????????????¨??????????????????)     */
    vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
};

/**
 * @brief ??°????????¨??¨??????(???)
 * @note  G = (V, E)???????????¢??°w???????????????????????°????????¨????????¨???
 *        ???(u, v) ??? E????????????w(u, v)??¨??¨?????????
 */
struct edge {
    index_t  src;   /**< ???????§????u */
    index_t  dst;   /**< ????????????v */
    union {
        weight_t w;     /**< ???(u, v)????????????(?????????) */
        capacity_t c;   /**< ???(u, v)????????? */
    };
    edge() = default;
    edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
    edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
};



using edges_t    = std::vector<edge>;      /**< ??°??????G=(V, E)????????????E   */
using vertices_t = std::vector<vertex>;    /**< ??°??????G=(V, E)???????????????V */
using array_t    = std::vector<weight_t>;  /**< ??????w?????????  */
using indices_t  = std::vector<index_t>;   /**< ????????????????????? */
using matrix_t   = std::vector<array_t>;   /**< ??°??????G?????£??\????????¨???(???????????¨????????¨???) */
using graph_t    = std::vector<edges_t>;   /**< ??°??????G?????£??\???????????¨???(???????????????????????¨??????) */



//****************************************
// ??¢??°?????????
//****************************************

/**
 * @brief  ??(V)???????¶????????????£??????????????¨????????¨???????????????????????????
 * @note   ??????????????????????????????v ??? V????????????v.?? = NIL???????????????v ??? V - {s}????????????v.d = ?????§??????
 */
static inline void initialize_single_source(vertices_t& V, index_t s)
{
    for (auto&& v : V) {
        v.d     = limits::inf;
        v.pi    = limits::nil;
    }
    V[s].d = 0;
}



/**
 * @brief  ???(u, v)?????????(relaxing)??????u????????±???????????¨??§v????????¢??\???????????????
 *         ????????§??????????????????????????????????????§??????????????°v.d??¨v.???????´??°??????
 *         ??????????????£??????????????¨??????v.d???????°???????v?????????????±???§v.???????´??°??????????????¨?????????
 *
 * @note   ??\????????????????????????(u, v)?????????????????(1)????????§????????????
 *         ????????????????¶????pred(V, u)?????(1)??§????????????????????¨???????????????
 *
 * @param  vertices_t& V   ????????????V
 * @param  index_t u       ???(u, v)????§????u (????????????u ??? V)
 * @param  index_t v       ???(u, v)?????????v (????????????v ??? V)
 * @param  weight_t w      ???(u, v)?????????w
 * @param  Predicate pred  relax????????????????????¶????¨???°????????°???
 */
static void relax(vertices_t& V,
           index_t u, index_t v, weight_t w,
           std::function<bool(const vertices_t&, index_t)> pred)
{
    if (pred(V, u) && V[v].d > V[u].d + w) {
        V[v].d = V[u].d + w;
        V[v].pi = u;
    }
}

// ??????????????????????????????relax??¢??°???

static void relax(vertices_t& V, const edge& e,
           std::function<bool(const vertices_t&, index_t)> pred)
{
    relax(V, e.src, e.dst, e.w, pred);
}
static void relax(vertices_t& V, const matrix_t& W,
           index_t u, index_t v,
           std::function<bool(const vertices_t&, index_t)> pred)
{
    relax(V, u, v, W[u][v], pred);
}



/**
 * @brief  Bellman-Ford??¢?????´?????????
 *
 * @note   Bellman-Ford??¢?????´??????????????????????????¨????¨±????????¬??????????§???????????????????????§£???
 *         ????????¢??°w: E -> R?????????????????????????????°??????G = (V, E)??¨?§????s????????????????????¨??????
 *         ?§????????????°?????????????????????????????¨???????????????????????????????????????Bellman-Ford??¢?????´??????????????????
 *         ??¢?????´???????????????????????????????????????????????¨????????°?§£????????¨???????????¨??±?????????????????§???????????°???????????¨???????????????????????????
 *
 * @note   Bellman-Ford??¢?????´??????????????????????¬????????????????????????¨??§????§????s???????????????v ??? V??????????????????????????¨??????v.d???
 *         ?????????????????????????´(s, v)????????´???????????§??????????????????
 *         ??¢?????´???????????????TRUE????????????????????°??????????§????????????°??????????????????????????????????????¨????????????????????¨????????????
 *
 * @note   Bellman-Ford??¢?????´??????????????(VE)????????§??°???
 *
 * @param  const graph_t& G ??°??????G
 * @param  index_t        s ?§????s
 */
std::pair<bool, vertices_t> bellman_ford(const graph_t& G, index_t s)
{   
    index_t n = G.size();
    vertices_t V(n);
    auto relax_pred = [] (const vertices_t& V, index_t u) -> bool { return V[u].d != limits::inf; };

    
    initialize_single_source(V, s);  // ?????????????????????d?????¨???????????????????????
    // ??¢?????´??????????????°???????????????????????????|V| - 1?????°?????????
    for (index_t i = 0; i < n - 1; ++i) {
        for (auto&& es : G) { for (auto&& e : es) {
                relax(V, e, relax_pred);  // ??°??????????????????????????????1???????????????
            }
        }
    }
    // G???s????????°?????????????????????????????????????????°?????????????????????????????????(u, v)???????????????
    //   u.d = ?´(s, v)
    //      <= ?´(s, u) + w(u, v) (??? ????§??????????)
    //       = u.d + w(u, v)
    // ????????????BELLMAN-FORD??????FALSE??????????????¨????????????TRUE?????????
    for (auto&& es : G) { for (auto&& e : es) {               // ???????????????????????????????????????????????????
            index_t v = e.dst, u = e.src;
            if (V[u].d != limits::inf && V[v].d > V[u].d + e.w) {  // G????§????s????????°????????????????????????????????¨??????
                return std::make_pair(false, V);       // FALSE?????????
            }
        }
    }
    // G???s????????°?????????????????????????????????????????°??????TRUE??????????????????????????????v ??? V?????????????´(s, v)??????????????????
    // ???????????¨?????°??????G?????s????????¨?????????????????¨??§??????
    return std::make_pair(true, V);
}



//****************************************
// ?????????????????????
//****************************************

GRAPH_END



//****************************************
// ??¨?????????????????????
//****************************************

int main(void)
{
    using namespace std;
    using namespace graph;
    int V, E, r;
    
    while (cin >> V >> E >> r) {
        graph_t G(V);
        for (int i = 0; i < E; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            G[a].emplace_back(a, b, c);
        }
        auto t = bellman_ford(G, r);
        if (t.first) {
            for (int i = 0; i < V; i++) {
                if (t.second[i].d > 1000000) { cout <<  "INF"; }
                else                         { cout << t.second[i].d;   }
                cout << endl;
            }
        }
        else {
            cout << "NEGATIVE CYCLE" << endl;
        }
    }
}

Measured memory_bytes: 3184