Shared code

#![allow(unused)]
 
fn main() {
    let inp = readv::<usize>();
    let (n, m) = (inp[0], inp[1]);
    let mut adj1 = vec![vec![]; n];
    let mut adj2 = vec![vec![]; n];
    for _ in 0..m {
        let edge = readv::<i64>();
        let u = edge[0] as usize - 1;
        let v = edge[1] as usize - 1;
        let w = -edge[2];
        adj1[u].push((v, w));
        adj2[u].push(v);
    }
 
    let (dis, _, cnt) = spfa(&adj1, vec![0], 10i64.pow(18));
 
    let neg_cycles_verts: Vec<usize> = (0..n).filter(|u| cnt[*u] == n).collect();
    let (dep, _) = bfs(&adj2, neg_cycles_verts, usize::MAX);
    if dep[n - 1] != usize::MAX {
        // if we can go from any vertex on the negative cycles to the destination, then no answer.
        println!("-1");
    } else {
        println!("{}", -dis[n - 1]);
    }
}
 
fn spfa(
    adj: &Vec<Vec<(usize, i64)>>,
    srcs: Vec<usize>,
    inf: i64,
) -> (Vec<i64>, Vec<usize>, Vec<usize>) {
    let n = adj.len();
    let mut dis = vec![inf; n];
    let mut inq = vec![false; n];
    let mut cnt = vec![0; n];
    let mut par = vec![!0; n];
    let mut que = std::collections::VecDeque::new();
 
    for src in srcs {
        dis[src] = 0;
        par[src] = src;
        inq[src] = true;
        que.push_back(src);
    }
 
    while let Some(u) = que.pop_front() {
        inq[u] = false;
        for &(v, w) in adj[u].iter() {
            let nd = dis[u] + w;
            if nd < dis[v] {
                dis[v] = nd;
                par[v] = u;
                cnt[v] += 1;
                if !inq[v] && cnt[v] < n {
                    inq[v] = true;
                    que.push_back(v);
                }
            }
        }
    }
 
    (dis, par, cnt)
}
 
fn bfs(adj: &Vec<Vec<usize>>, srcs: Vec<usize>, inf: usize) -> (Vec<usize>, Vec<usize>) {
    let n = adj.len();
    let mut dep = vec![inf; n];
    let mut par = vec![!0; n];
    let mut que = std::collections::VecDeque::new();
 
    for src in srcs {
        dep[src] = 0;
        par[src] = src;
        que.push_back(src);
    }
 
    while let Some(u) = que.pop_front() {
        for &v in adj[u].iter() {
            if dep[v] == inf {
                dep[v] = dep[u] + 1;
                par[v] = u;
                que.push_back(v);
            }
        }
    }
 
    (dep, par)
}
 
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
 
fn readv<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_ascii_whitespace()
        .map(|t| t.parse().ok().unwrap())
        .collect()
}
 
fn reads() -> Vec<char> {
    read::<String>().chars().collect()
}
 
fn mapv<T, S, F: Fn(&T) -> S>(arr: &Vec<T>, f: F) -> Vec<S> {
    arr.iter().map(f).collect()
}
 
fn join<T: ToString>(arr: &[T], sep: &str) -> String {
    arr.iter()
        .map(|x| x.to_string())
        .collect::<Vec<String>>()
        .join(sep)
}