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::cmp::min;

pub fn warshall_floyd_apsp<'a,V,E,G,W,F>(g: &'a G,fp: F) -> Vec<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![vec![None; n];n];

    for v in 0..n {
        dist[v][v] = Some(W::zero());
        for e in g.delta(&Vite(v)) {
            let u = to(Vite(v), g.edge(e)).0;
            dist[v][u] = Some(fp(g.edge(e)));
        }
    }

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                dist[i][j] = match (dist[i][j], dist[i][k], dist[k][j]){
                    (None, Some(d1), Some(d2)) => Some(d1 + d2),
                    (Some(d), Some(d1), Some(d2)) => Some(min(d1 + d2, d)),
                    (d, _, _) => d
                }
            }
        }
    }

    dist
}
struct Ver {
    i: usize
}
  
impl Vertex for Ver {
    fn new(id: usize) -> Self {
        Ver {
            i: id
        }
    }
    fn id(&self) -> usize { self.i }
}
  
struct WEdge {
    from: Vite,
    to: Vite,
    dist: i64
}
  
impl Edge for WEdge {
    fn from(&self) -> Vite { self.from } 
    fn to(&self) -> Vite { self.to }
}
   
 
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) = (v[0] , v[1]);
    let mut g = DirectedGraph::<Ver,WEdge>::new(n);
   
    for _ in 0..m {
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let a:Vec<i64> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (x,y,w) = (a[0] as usize,a[1] as usize,a[2]);
        g.add_edge(WEdge{ from: Vite(x), to: Vite(y), dist: w });
    }
    let res = warshall_floyd_apsp(&g, |e| e.dist);
    for i in 0..n {
        if let Some(x) = res[i][i] {
            if x < 0 {
                println!("NEGATIVE CYCLE");
                return;
            }
        }
    }

    for i in 0..n {
        for j in 0..n {
            match res[i][j] {
                Some(d) => print!("{}", d),
                None => print!("INF")
            }
            if j < n - 1 { print!(" "); }
        }
        println!("");
    }
}
   



Measured memory_bytes: 5060