#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;
using System.Timers;

static class MainClass
{
    public static void Main(string[] args)
    {
        var VEr = Console.ReadLine().SplittedStringToInt32List();
        var v = VEr[0];
        var e = VEr[1];
        var r = VEr[2];
        var edges = new Edge[e];
        for (int i = 0; i < e; i++)
        {
            var str = Console.ReadLine().SplittedStringToInt32List();
            edges[i] = new Edge() { Cost = str[2], From = str[0], To = str[1] };
            
        }
        InitializeBellmanFord(v, e, edges);
        if (HasNegativeLoopFromS(r))
        {
            Console.WriteLine("NEGATIVE CYCLE");
        }
        else
        {
            SearchShortestPath(r);

       
            foreach (var item in ShortestDistances)
            {
                if (item == INF)
                {
                    Console.WriteLine("INF");
                }
                else
                {
                    Console.WriteLine(item);
                }
            }


        }

        Console.ReadLine();
    }
        // s番目の頂点から各々の頂点への最短距離を求めるBellman-Ford

    public static void InitializeBellmanFord(int v, int e, IEnumerable<Edge> edges)
    {
        V = v;
        Edges = edges.ToArray();
        ShortestDistances = new int[V];
        E = e;
    }

    public class Edge
    {
        public int From;
        public int To;
        public int Cost;
    }

    public static Edge[] Edges;

    public static int[] ShortestDistances;

    public static int V;

    public static int E;

    public static void SearchShortestPath(int s)
    {
        for (int i = 0; i < V; i++)
        {
            ShortestDistances[i] = INF;
        }
        ShortestDistances[s] = 0;
        while (true)
        {
            var update = false;
            for (int i = 0; i < E; i++)
            {
                var e = Edges[i];
                if (ShortestDistances[e.From] != INF && ShortestDistances[e.To] > ShortestDistances[e.From] + e.Cost)
                {
                    ShortestDistances[e.To] = ShortestDistances[e.From] + e.Cost;
                    update = true;
                }
            }
            if (!update)
                break;
        }
    }

    // 負閉路をもつか？
    public static bool HasNegativeLoopAllgraph()
    {
        var d = new int[V];
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < E; j++)
            {
                var e = Edges[j];
                if (d[e.To] > d[e.From] + e.Cost)
                {
                    d[e.To] = d[e.From] + e.Cost;
                    if (i == V - 1)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    // 負閉路をもつか？（start固定）
    public static bool HasNegativeLoopFromS(int s)
    {
        var d = new int[V];
        for (int i = 0; i < V; i++)
        {
            d[i] = INF;
        }
        d[s] = 0;
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < E; j++)
            {
                var e = Edges[j];
                if (d[e.From] != INF && d[e.To]>d[e.From] + e.Cost)
                {
                    d[e.To] = d[e.From] + e.Cost;
                    if (i == V - 1)
                        return true;
                }
            }
        }
        return false;
    }
    // 負閉路をもつか？(start,destination固定)
    public static bool HasNegativeLoopFromSToG(int s, int g)
    {
        var d = new int[V];
        for (int i = 0; i < V; i++)
        {
            d[i] = INF;
        }
        d[s] = 0;
        for (int i = 0; i < 2* V; i++)
        {
            for (int j = 0; j < E; j++)
            {
                var e = Edges[j];
                if (d[e.From] != INF && d[e.To] > d[e.From] + e.Cost)
                {
                    d[e.To] = d[e.From] + e.Cost;
                    if (i >= V - 1 && e.To == g)
                        return true;
                }
            }
        }
        return false;
    }




    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();

    public const int INF = int.MaxValue / 2;
    #endregion
}



Measured memory_bytes: 18504