use std::{array::from_fn, rc::Rc};

#[derive(Clone, Copy)]
pub struct Line {
    a: i64,
    b: i64,
}

impl Line {
    fn new(a: i64, b: i64) -> Self {
        Self { a, b }
    }

    fn aligned(&self, r: &Self, rr: &Self) -> bool {
        ((r.b - self.b) as i128 * (self.a - rr.a) as i128
            - (self.a - r.a) as i128 * (rr.b - self.b) as i128)
            < 0
    }

    fn eval(&self, x: i128) -> i128 {
        self.a as i128 * x + self.b as i128
    }
}

#[derive(Clone)]
pub struct Node {
    val: Line,
    prev: Vec<Rc<Node>>,
}

impl Node {
    fn new(l: &Line) -> Self {
        Node {
            val: *l,
            prev: vec![],
        }
    }

    fn link(&mut self, prev: Rc<Node>) {
        self.prev.push(Rc::clone(&prev));

        for i in 0.. {
            if let Some(anc) = self.prev[i].prev.get(i) {
                self.prev.push(Rc::clone(anc));
            } else {
                break;
            }
        }

        assert!(self.prev.len() < 30);
    }
}

mod persistent_cht {
    use crate::*;
    pub fn insert(mut top: Rc<Node>, line: Line) -> Rc<Node> {
        let mut node = Node::new(&line);

        while !top.prev.is_empty() {
            let prev = top.prev[0].val;

            if !prev.aligned(&top.val, &line) {
                top = Rc::clone(&top.prev[0]);
            } else {
                break;
            }
        }

        node.link(top);

        // eprintln!("prev len = {}", node.prev.len());

        Rc::new(node)
    }

    pub fn max_eval(mut top: Rc<Node>, x: i128) -> i128 {
        if top.prev.is_empty() {
            return top.val.eval(x);
        }

        let l = top.prev.len() - 1;

        for k in (0..=l).rev() {
            if let Some(anc) = top.prev.get(k) {
                if let Some(panc) = anc.prev.first() {
                    if panc.val.eval(x) > anc.val.eval(x) {
                        top = Rc::clone(anc);
                    }
                }
            }
        }

        top.val
            .eval(x)
            .max(top.prev.get(0).map_or(i128::MIN, |p| p.val.eval(x)))
    }
}

struct SegNode {
    node: Rc<Node>,
    left: Option<Rc<SegNode>>,
    right: Option<Rc<SegNode>>,
}

impl SegNode {
    fn insert(now: Option<Rc<SegNode>>, s: usize, e: usize, x: usize, l: &Line) -> Rc<SegNode> {
        Rc::new({
            if let Some(now) = now {
                let node = persistent_cht::insert(Rc::clone(&now.node), *l);

                let (left, right) = if s != e {
                    let m = (s + e) >> 1;
                    if x <= m {
                        (
                            Some(Self::insert(
                                now.left.as_ref().map(|x| Rc::clone(x)),
                                s,
                                m,
                                x,
                                l,
                            )),
                            now.right.as_ref().map(|x| Rc::clone(x)),
                        )
                    } else {
                        (
                            now.left.as_ref().map(|x| Rc::clone(x)),
                            Some(Self::insert(
                                now.right.as_ref().map(|x| Rc::clone(x)),
                                m + 1,
                                e,
                                x,
                                l,
                            )),
                        )
                    }
                } else {
                    (None, None)
                };

                Self { node, left, right }
            } else {

                let (left, right) = if s != e {
                    let m = (s + e) >> 1;
                    if x <= m {
                        (
                            Some(Self::insert(
                                None,
                                s,
                                m,
                                x,
                                l,
                            )),
                            None,
                        )
                    } else {
                        (
                            None,
                            Some(Self::insert(
                                None,
                                m + 1,
                                e,
                                x,
                                l,
                            )),
                        )
                    }
                } else {
                    (None, None)
                };

                Self {
                    node: Rc::new(Node::new(l)),
                    left: left,
                    right: right,
                }
            }
        })
    }

    fn query_max(
        now: Option<Rc<SegNode>>,
        s: usize,
        e: usize,
        l: usize,
        r: usize,
        x: i128,
    ) -> i128 {
        // eprintln!(
        //     "node ok?: {}, s, e = [{}, {}], [l, r] = [{}, {}], x = {}",
        //     now.is_some(),
        //     s,
        //     e,
        //     l,
        //     r,
        //     x
        // );

        if let Some(now) = now {
            let ret = {
                if r < s || e < l {
                    i128::MIN
                } else if l <= s && e <= r {
                    // eprintln!(
                    //     "evaluating CHT for se=[{},{}], lr=[{},{}], x={}",
                    //     s, e, l, r, x
                    // );
                    persistent_cht::max_eval(Rc::clone(&now.node), x)
                } else {
                    let m = (s + e) >> 1;
                    Self::query_max(now.left.as_ref().map(|x| Rc::clone(&x)), s, m, l, r, x).max(
                        Self::query_max(
                            now.right.as_ref().map(|x| Rc::clone(x)),
                            m + 1,
                            e,
                            l,
                            r,
                            x,
                        ),
                    )
                }
            };
            // eprintln!("ans = {}", ret);
            ret
        } else {
            i128::MIN
        }
    }
}

fn solve(stdin: &str) {
    let mut tokens = stdin.split_whitespace();
    let mut next = || tokens.next().unwrap();

    let [n, _]: [usize; 2] = from_fn(|_| next().parse().unwrap());
    let mut dep = vec![0; n];

    let mut dep_comp = vec![0];

    let d = (1..n)
        .map(|i| {
            let [f, s, p, q, mut l]: [i64; 5] = from_fn(|_| next().parse().unwrap());

            let f = (f - 1) as usize;

            assert!(f < i);

            dep[i] = dep[f] + s;
            l = l.min(dep[i]);

            dep_comp.push(dep[i]);
            dep_comp.push(dep[i] - l);

            (f, p, q, l)
        })
        .collect::<Vec<_>>();

    dep_comp.sort();
    dep_comp.dedup();

    let m = dep_comp.len();

    let mut roots = vec![SegNode::insert(None, 0, m - 1, 0, &Line::new(0, 0))];

    for (i, &(f, p, q, l)) in d.iter().enumerate() {
        let i = i + 1; // index gap
        let root = Rc::clone(&roots[f]);

        let ei = dep_comp.binary_search(&dep[i]).unwrap();
        let si = dep_comp.binary_search(&(dep[i] - l)).unwrap();

        let mut base = (q as i128) + (dep[i] as i128) * (p as i128);

        // eprintln!("base = {}", base);

        base -= {
            let qv = SegNode::query_max(Some(Rc::clone(&root)), 0, m - 1, si, ei, p as i128);
            // eprintln!("query value = {}", qv);
            qv
        };

        println!("{}", base);

        roots.push(SegNode::insert(
            Some(root),
            0,
            m - 1,
            ei,
            &Line::new(dep[i], -base as i64),
        ));
    }
}

thread_local! {
    static STDOUT: std::cell::RefCell<std::io::BufWriter<std::io::StdoutLock<'static>>> = std::cell::RefCell::new(std::io::BufWriter::with_capacity(1 << 17, std::io::stdout().lock()));
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|refcell| {
            use std::io::*;
            writeln!(refcell.borrow_mut(), $($t)*).unwrap();
        });
    };
}
#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        STDOUT.with(|refcell| {
            use std::io::*;
            write!(refcell.borrow_mut(), $($t)*).unwrap();
        });
    };
}

fn main() {
    use std::io::*;
    solve(&read_to_string(stdin()).unwrap());
    STDOUT.with(|refcell| std::io::Write::flush(&mut *refcell.borrow_mut()).unwrap());
}