今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。

　　全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 f_v  以及到父亲城市道路的长度 s_v。

　　从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。

　　对于任意一个城市 v，我们会给出一个交通工具的距离限制 l_v。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 l_v  时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 p_v,q_v  作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dp_v+q_v。

　　每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

#include <cstdio>

#include <algorithm>

#define l(a) (son[a][0])

#define r(a) (son[a][1])

#define ll long long

#define INF 1LL<<62

#define MM 7400005

#define MN 200005

#define MS 19

using namespace std;

struct node

{

    int pos; double slope;

    friend node operator+(const node& a,const node& b){return b.pos?b:(node){,};}

}t[MM],g[MN][MS];

struct edge{int nex,to; ll wt;}e[MN];

int pin,din,n,tp,MO;

int hr[MN],a[MN],rt[MN*],st[MN],son[MM][];

int cg[MN][MS][MS],bh[MN][MS];

ll f[MN],s[MN],lim[MN],b[MN];

inline ll read()

{

    ll n=,f=; char c=getchar();

    while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}

    while (c>='' && c<='') {n=n*+c-''; c=getchar();}

    return n*f;

}

inline void ins(int x,int y,ll z) {e[++pin]=(edge){hr[x],y,z}; hr[x]=pin;}

node Tgetans(int x,int L,int R,int z)

{

    if (!x||L==R) return (node){,};

    int mid=L+R>>;

    if (!t[l(x)].pos||z<t[l(x)].slope) return Tgetans(l(x),L,mid,z);

    else {node lt=Tgetans(r(x),mid+,R,z); return lt.pos?lt:t[l(x)];}

}

void Tmodify(int& x,int L,int R,int y,int z,int pre,int depth)

{

    if (!x) x=++din;

    if (L==R) {g[y][z]=t[x]; bh[y][z]=L; t[x]=(node){y,pre?(double)(f[y]-f[pre])/(s[y]-s[pre]):}; return;}

    int mid=L+R>>;

    if (t[l(x)].pos&&(double)(f[y]-f[t[l(x)].pos])/(s[y]-s[t[l(x)].pos])>t[l(x)].slope) Tmodify(r(x),mid+,R,y,z,t[l(x)].pos,depth+);

    else {Tmodify(l(x),L,mid,y,z,pre,depth+); cg[y][z][depth]=r(x); r(x)=;}

    t[x]=t[l(x)]+t[r(x)];

}

void Tcance(int x,int L,int R,int y,int z,int depth)

{

    if (L==R) {t[x]=g[y][z]; return;}

    int mid=L+R>>;

    if (bh[y][z]>mid) Tcance(r(x),mid+,R,y,z,depth+);

    else {Tcance(l(x),L,mid,y,z,depth+); r(x)=cg[y][z][depth];}

    t[x]=t[l(x)]+t[r(x)];

}

void getans(int x,int ql,int qr,int z)

{

    node lt; f[x]=INF;

    register int j;

    for (j=,ql+=MO,qr+=MO;ql<=qr;ql>>=,qr>>=,j<<=)

    {

        if ( ql&)

        {

            if (t[rt[ql]].pos&&z>=t[rt[ql]].slope) lt=t[rt[ql++]];

            else lt=Tgetans(rt[ql++],,j,z);

            f[x]=min(f[x],f[lt.pos]+(s[x]-s[lt.pos])*z+b[x]);

        }

        if (~qr&)

        {

            if (t[rt[qr]].pos&&z>=t[rt[qr]].slope) lt=t[rt[qr--]];

            else lt=Tgetans(rt[qr--],,j,z);

            f[x]=min(f[x],f[lt.pos]+(s[x]-s[lt.pos])*z+b[x]);

        }

    }

}

void modify(int x,int q)

{

    register int i,j;

    for (i=,j=,q+=MO;q;q>>=,++i,j<<=) Tmodify(rt[q],,j,x,i,,);

}

void cance(int x,int q)

{

    register int i,j;

    for (i=,j=,q+=MO;q;q>>=,++i,j<<=) Tcance(rt[q],,j,x,i,);

}

void dfs(int x)

{

    register int i,L,R;

    for (L=,R=tp;L<R;)

    {

        int mid=L+R>>;

        if (s[x]-s[st[mid]]>lim[x]) L=mid+; else R=mid;

    }

    if (R) getans(x,R,tp,a[x]);

    st[++tp]=x; modify(x,tp);

    for (i=hr[x];i;i=e[i].nex)

    {

        s[e[i].to]=s[x]+e[i].wt;

        dfs(e[i].to);

    }

    cance(x,tp); --tp;

}

int main()

{

    register int i,x;

    register ll y;

    n=read(); x=read();

    for (MO=;MO<n;MO<<=); --MO;

    for (i=;i<=n;++i)

    {

        x=read(); y=read(); ins(x,i,y);

        a[i]=read(); b[i]=read(); lim[i]=read();

    }

    dfs();

    for (i=;i<=n;++i) printf("%lld\n",f[i]);

}