pub trait Property: Copy {}

impl<P> Property for P where P: Copy {}

pub trait ZeroP {
    fn zero() -> Self;
}

impl ZeroP for usize { fn zero() -> Self { 0 } }
impl ZeroP for u8 { fn zero() -> Self { 0 } }
impl ZeroP for u16 { fn zero() -> Self { 0 } }
impl ZeroP for u32 { fn zero() -> Self { 0 } }
impl ZeroP for u64 { fn zero() -> Self { 0 } }
impl ZeroP for isize { fn zero() -> Self { 0 } }
impl ZeroP for i8 { fn zero() -> Self { 0 } }
impl ZeroP for i16 { fn zero() -> Self { 0 } }
impl ZeroP for i32 { fn zero() -> Self { 0 } }
impl ZeroP for i64 { fn zero() -> Self { 0 } }

pub trait Weighted: Property + std::ops::Add<Output=Self> + std::cmp::Ord + ZeroP {}

impl<W> Weighted for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord + ZeroP {}

pub trait NonNegativeWeighted: Weighted {}

impl NonNegativeWeighted for usize {}

pub trait Capacity: Weighted + std::ops::Sub<Output=Self>{}

impl Capacity for usize {}

pub trait Cost: Capacity + std::ops::Mul<Output=Self> {}

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Vite(pub usize);

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Eite(pub usize);

pub trait Edge {
    fn from(&self) -> Vite;
    fn to(&self) -> Vite;
}

pub trait Vertex {
    fn new(id : usize) -> Self;
    fn id(&self) -> usize;
}

impl Vertex for usize {
    fn new(id: usize) -> Self { id }
    fn id(&self) -> usize { *self }
}

impl Edge for (usize,usize) { 
    fn from(&self) -> Vite { Vite(self.0) }
    fn to(&self) -> Vite { Vite(self.1) }
}

impl<P> Edge for (usize,usize,P) where P: Property { 
    fn from(&self) -> Vite { Vite(self.0) }
    fn to(&self) -> Vite { Vite(self.1) }
}

pub trait Graph<'a, V: Vertex, E: Edge> {
    type EsIter: std::iter::Iterator<Item=&'a Eite>;
    fn add_edge(&mut self, e: E);
    fn delta(&'a self, v: &Vite) -> Self::EsIter;
    fn edge(&self, e: &Eite) -> &E;
    fn vertex(&self, v: &Vite) -> &V;
    fn v_size(&self) -> usize;
    fn e_size(&self) -> usize;
}

pub fn from<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.from() }
    else { e.to() }
}

pub fn to<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.to() }
    else { e.from() }
}

pub trait Directed<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }
pub trait Undirected<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }
pub trait Bipartite<'a,V: Vertex, E: Edge>: Graph<'a,V,E> { 
    fn left_size(&self) -> usize;
    fn right_size(&self) -> usize;
    fn left_vs(&self) -> std::slice::Iter<Vite>;
    fn right_vs(&self) -> std::slice::Iter<Vite>;
}

pub struct DirectedGraph<V: Vertex, E: Edge> {
    n: usize,
    m: usize,
    g: Vec<Vec<Eite>>,
    es: Vec<E>,
    vs: Vec<V>
}

impl<'a,V: Vertex, E: Edge> Graph<'a,V,E> for DirectedGraph<V,E> {
    type EsIter = std::slice::Iter<'a,Eite>;
    fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().0].push(ei);
        self.es.push(e);
    }
    fn delta(&'a self, v: &Vite) -> Self::EsIter {
        self.g[v.0].iter()
    }
    fn edge(&self, e: &Eite) -> &E {
        &self.es[e.0]
    }
    fn vertex(&self, v: &Vite) -> &V {
       &self.vs[v.0]
    }
    fn v_size(&self) -> usize {
        self.n
    }
    fn e_size(&self) -> usize {
        self.m
    }
}

impl<'a,V: Vertex, E: Edge> Directed<'a,V,E> for DirectedGraph<V,E> {  }

impl<V: Vertex, E: Edge> DirectedGraph<V,E> {
    pub fn new(n: usize) -> Self {
        let mut g = DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Eite>::new(); n],
            es: Vec::<E>::new(),
            vs: Vec::<V>::new()
        };
        for i in 0..n {
            g.vs.push(V::new(i));
        }
        g
    }
}

use std::collections::VecDeque;

pub fn spfa_s3p<'a,V,E,G,W,F>(g: &'a G, s: Vite, fp: F) -> Option<Vec<Option<W>>>
where V: Vertex, E: Edge, G: Graph<'a,V,E>, W: Weighted, F: Fn(&E) -> W {
    let n = g.v_size();
    let mut dist = vec![None; n];
    let mut que = VecDeque::new();
    let mut inc = vec![false; n];
    let mut cnt = vec![0; n];
    dist[s.0] = Some(W::zero());
    que.push_back(s);
    inc[s.0] = true;
    cnt[s.0] += 1;
    while let Some(v) = que.pop_back() {
        inc[v.0] = false;
        let d = dist[v.0].unwrap();
        for ei in g.delta(&v) {
            let e = g.edge(ei);
            let to = to(v, e);
            let cost = fp(e);
            if match dist[to.0] {
                Some(d2) => { cost + d < d2 }
                None => true
            } {
                dist[to.0] = Some(cost + d);
                if !inc[to.0] {
                    que.push_back(to);
                    inc[to.0] = true;
                    cnt[to.0] += 1;
                    if cnt[to.0] >= n { return None; }
                }
            }
        }
    }
    Some(dist)
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n,m,r) = (v[0] , v[1] , v[2]);
    let mut g = DirectedGraph::<usize, (usize,usize,i64)>::new(n);
    for _ in 0..m{
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let x:Vec<i64> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (v,u,d) = (x[0],x[1],x[2]);
        g.add_edge((v as usize ,u as usize,d));
    }
    if let Some(res) = spfa_s3p(&g, Vite(r), |ep| ep.2) {
        for d in res {
            match d {
                Some(i) => println!("{}" , i),
                None => println!("INF")
            }
        }
    }
    else {
        println!("NEGATIVE CYCLE");
    }
}



Measured memory_bytes: 5052