• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

آقای ـــــ به تازگی به ریاست یک سازمان فوقِ فوقِ مافوقِ سرّی درآمده است! امّا چند صباحی است که از منبعی موثّق شنیده در آن سازمان یک نفر مشغول جاسوسی است. نام‌برده از آن روز تا همین لحظه آرام و قرار ندارد؛ حتّی نزدیکانش نقل کرده‌اند از فرط اضطراب، آمار مصرف قرص‌های اعصابش سر به فلک کشیده است.

مشاوران آقای ـــــ که بسیار نگران حال وی هستند، تصمیم گرفتند جاسوس را بیابند بلکه حال عمومی او بهبود یابد. تعداد کارمندان اداره بسیار زیاد است و برای جمعیت اندک مشاوران و معتمدان آقای ـــــ ، پیدا کردن جاسوس از بین این حجم کارمند، مانند پیدا کردن سوزنی در انبار کاه است. لذا آن‌ها تصمیم گرفتند از هر کارمند بخواهند اگر در میان افراد زیردستش به کسی مشکوک است، نام آن را سریعا اعلام کند.

در این اداره هر کارمند به جز آقای ـــــ یک مدیر دارد. فرض کنید کارمندان را با اعداد طبیعی از ۱ تا \(n\) شماره‌گذاری کرده‌ایم.(آقای ـــــ هم یکی از این \(n\) کارمند است) شماره‌ی مدیر کارمند \(i\)ام را با \(m_i\) نشان می‌دهیم. \(m\) به ازای آقای ـــــ نیز برابر با \(-1\) خواهد بود. هم‌چنین هر کارمند یک میزان اعتبار در اداره دارد. اعتبار کارمند \(i\)ام را \(c_i\) می‌نامیم. هم‌چنین اگر کسی بخواهد بررسی کند که کارمند \(i\)ام جاسوس است یا نه، نیاز به صرف \(t_i\) دقیقه وقت دارد.

می‌گوییم کارمند \(A\) زیردست کارمند \(B\) است، در صورتی که \(B\) مدیر \(A\) باشد و یا کارمندی که مدیر \(A\) است، زیردست \(B\) باشد.

هر کارمند برای بررسی وجود جاسوس در بین زیردستانش، باید تمام زیردستانش که اعتبارشان از اعتبار او کم‌تر است را بررسی کند و همان طور که گفته شد برای بررسی هر یک از آن‌ها نیاز به مقداری وقت دارد. شما باید به ازای هر کارمند بگویید چه قدر طول می‌کشد تا آن کارمند زیردستانش را بررسی کند.

پ.ن.: نام آقای ـــــ به دلیل درخواست مکرّر مراجع قضایی از صورت سوال حذف گشت.

ویرایش: در این سوال ممکن نیست به ازای دو کارمند، کارمند اول زیردست کارمند دوم باشد و کارمند دوم زیر دست کارمند اوّل باشد.

ورودی

در سطر اوّل ورودی عدد \(n\) می‌آید.

در هر یک از \(n\) خط بعد به ترتیب سه عدد \(m_i\) و \(c_i\) و \(t_i\) می‌آیند.

\[1 \le n, t_i, c_i \le 100 000\]

خروجی

در خط \(i\)ام از \(n\) خط خروجی، زمانی که طول می‌کشد کارمند \(i\)ام زیردستانش با اعتبار کم‌تر را بررسی کند را چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۵	\(n \le 5000\)
۲	۱۰	اعتبار هر کارمند از زیردستانش بیش‌تر است
۳	۲۰	هر کارمند زیردست حداکثر ۲۰ نفر دیگر است
۴	۶۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5
4 4 80
1 1 40
-1 10 60
3 5 50
4 8 70 

خروجی نمونه ۱

40
0
240
120
0