1 /**************************************************************
 2     Problem: 3672
 3     User: hzoier
 4     Language: C++
 5     Result: Accepted
 6     Time:9748 ms
 7     Memory:17924 kb
 8 ****************************************************************/
 9 #include<cstdio>
10 #include<cstring>
11 #include<algorithm>
12 #include<vector>
13 using namespace std;
14 const int maxn=200010;
15 const long double eps=1e-12;
16 void dfs(int);
17 void solve(int);
18 int getcenter(int);
19 int bfs(int);
20 int getpoint(long long);
21 long double getk(int,int);
22 bool cmp(int,int);
23 vector<int>G[maxn];
24 int p[maxn],size[maxn],son[maxn],s[maxn],top,q[maxn],vis[maxn]={0},tim=0;
25 long long f[maxn],d[maxn],b[maxn],l[maxn];
26 int n,a[maxn];
27 int main(){
28     memset(f,63,sizeof(f));
29     scanf("%d%*d",&n);
30     for(int i=2;i<=n;i++){
31         scanf("%d%lld%d%lld%lld",&p[i],&d[i],&a[i],&b[i],&l[i]);
32         G[p[i]].push_back(i);
33         d[i]+=d[p[i]];
34     }
35     f[1]=0;
36     solve(1);
37     for(int i=2;i<=n;i++)printf("%lld\n",f[i]);
38     return 0;
39 }
40 void solve(int x){
41     x=bfs(x);
42     vis[x]=++tim;
43     if(p[x]&&!vis[p[x]]){
44         int u=x;
45         while(p[u]&&!vis[p[u]])u=p[u];
46         solve(u);
47         for(u=p[x];u&&(!vis[u]||vis[u]>vis[x])&&d[u]>=d[x]-l[x];u=p[u])f[x]=min(f[x],f[u]+a[x]*(d[x]-d[u])+b[x]);
48     }
49     bfs(x);
50     sort(q+1,q+size[x],cmp);
51     int i=1;
52     while(i<size[x]&&d[x]<d[q[i]]-l[q[i]])i++;
53     s[top=1]=x;
54     for(x=p[x];i<size[q[0]];i++){
55         while(x&&(!vis[x]||vis[x]>vis[q[0]])&&d[x]>=d[q[i]]-l[q[i]]){
56             while(top>1&&getk(x,s[top])+eps>getk(s[top],s[top-1]))top--;
57             s[++top]=x;
58             x=p[x];
59         }
60         int j=getpoint(a[q[i]]);
61         f[q[i]]=min(f[q[i]],f[j]+a[q[i]]*(d[q[i]]-d[j])+b[q[i]]);
62     }
63     x=q[0];
64     for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])solve(G[x][i]);
65 }
66 int bfs(int x){
67     int head=0,tail=0;
68     q[tail++]=x;
69     while(head!=tail){
70         x=q[head++];
71         size[x]=1;
72         son[x]=0;
73         for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])q[tail++]=G[x][i];
74     }
75     for(int i=tail-1;i;i--){
76         size[p[q[i]]]+=size[q[i]];
77         if(size[q[i]]>size[son[p[q[i]]]])son[p[q[i]]]=q[i];
78     }
79     x=q[0];
80     int s=size[x];
81     while(son[x]&&(size[son[x]]<<1)>s)x=son[x];
82     return x;
83 }
84 int getpoint(long long k){
85     if(top<=1)return s[top];
86     int L=1,R=top-1;
87     while(L<=R){
88         int M=(L+R)>>1;
89         if(getk(s[M],s[M+1])-eps<k)R=M-1;
90         else L=M+1;
91     }
92     return s[L];
93 }
94 inline long double getk(int i,int j){return (long double)(f[i]-f[j])/(d[i]-d[j]);}
95 bool cmp(int x,int y){return d[x]-l[x]>d[y]-l[y];}