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

---

نادرشاه قصد لشکر کشی به کل دنیا برای فتح غنائم را دارد. هر کشور قابل نمایش به صورت یک گراف درخت است که در آن شهرها رئوس گراف و راه بین شهرها یال‌های درخت است. در هر شهر مثل $v$ تعداد $C_v$ الماس وجود دارد که اگر لشکری از نادرشاه به آن شهر برسد همه الماس‌های آن را غارت می‌کند.

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

توجه کنید ممکن است به یک شهر چند لشکر حمله کنند ولی اولا تنها یکبار الماس‌های آن غارت می‌شود و ثانیا هیچ لشکری دوبار به آن حمله نمی‌کند.

مسلما نادرشاه آنقدر باهوش هست که نیاز به کمک شما در استراتژی حمله نداشته باشد. به تاریخ‌دانان بگویید نادر چه تعداد الماس از هر جنگ غارت کرده!

ورودی

در سطر اول ورودی $t$ تعداد کشورهای مورد هجوم نادرشاه می‌آید و سپس اطلاعات $t$ کشور می‌آید. $$ 1 \le t \le 194$$ در سطر اول برای کشور $i$ به ترتیب سه عدد صحیح با فاصله می‌آید که عدد اول نشانگر تعداد شهر $N_i$، عدد دوم شهر ورودی لشکرها $I_i$ و عدد سوم تعداد لشکرهای نادرشاه $A_i$ است. $$ 1 \le I_i, A_i \le N_i$$ $$ \sum_{i=1}^t N_i \le 100 , 000$$ $$ \sum_{i=1}^t A_i \le 2000$$ سپس در سطر بعد $N_i$ عدد با فاصله می‌آید که $j$مین عدد نشانگر $C_{j_i}$ تعداد الماس‌های شهر $j$ در کشور $i$ است. $$ 0 \le C_{j_i} \le 10 , 000$$ سپس در $N_i - 1$ سطر بعد در هر سطر دو عدد $u_i$ و $v_i$ می‌آید که نشان می‌دهد شهر $u$ و $v$ در کشور $i$ به هم متصل هستند. $$ 1 \le u_i, v_i \le N_i$$

خروجی

در سطر $i$ از $t$ سطر خروجی حداکثر تعداد الماس‌های ممکن از غارت کشور $i$ را بنویسید.

مثال

ورودی نمونه ۱

3
5 3 2
1 2 3 4 5
1 3
3 2
4 3
3 5
5 1 2
1 0 3 1 1
1 2
1 3
3 4
3 5
3 1 2
0 25 75
1 2
2 3

خروجی نمونه ۱

12
6
100