هیئت مدیره‌ی شرکت الفبا، برای افزایش صمیمیت بین کارمندانش، تصمیم به برگزاری تعدادی مهمانی گرفته است. می‌دانیم که در این شرکت، هر فرد (به جز مدیرعامل) دقیقا یک مسئول دارد. هم‌چنین کارمند $x$ را ارشد کارمند $y$‌ می‌گوییم اگر حداقل یکی از دو شرط زیر برقرار باشد:

• $x$ مسئول $y$ باشد.
• $x$ ارشد $z$ باشد، به طوری‌که $z$ مسئول $y$ است.

این شرکت قصد دارد تعدادی مهمانی برگزار کند که در آن‌ها هر فرد (به جز مدیر عامل) با مسئولش، حداقل در یک مهمانی حضور داشته باشند. با توجه به سیاست‌های شرکت، تنها $m$ مهمانی قابل برگزاری است که هر کدام از آن‌ها را می‌توان با سه تایی $(u,v,c)$ نمایش داد. معنای این سه‌تایی این است که هزینه‌ی برگزاری مهمانی برابر با $c$ تومان است و افرادی

• $u$ و $v$ به مهمانی دعوت می‌شوند.
• تمامی کارمندان شرکت مانند $w$ به طوری‌که $v$ ارشد $w$ باشد و $w$ ارشد $u$ باشد، به مهمانی دعوت می‌شوند.

هم‌چنین می‌دانیم که در هر مهمانی مانند $(u,v,c)$، کارمند $v$، ارشد کارمند $u$‌ است.

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

لازم به ذکر است که شرکت الفبا شامل $n$‌ کارمند است که با شماره‌های $1$ تا $n$‌ شماره‌گذاری شده‌اند و مدیرعامل شرکت با عدد $1$ مشخص شده است.

سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد کارمندان شرکت و $m$، تعداد مهمانی‌های قابل برگزاری شرکت، آمده است.

سطر دوم شامل $n-1$‌ عدد طبیعی $p_2,p_3,\cdots,p_n$ است به طوری‌که $p_i$ نشان‌دهنده‌ی مسئول کارمند شماره‌ی $i$ است.

در هر یک از $m$ سطر بعدی به ترتیب سه عدد طبیعی $u$، $v$ و $c$ آمده است که نشان‌دهنده‌ی یک مهمانی با سه تایی $(u,v,c)$ است.

در تنها سطر خروجی کمترین هزینه برای رسیدن به خواسته‌ی شرکت را چاپ کنید.

• زیرمسئله اول (۶ نمره): $n\leq 100,m\leq 100$
• زیرمسئله دوم (۸ نمره): $n\leq 3000, m\leq 3000$
• زیرمسئله سوم (۱۵ نمره): $n\leq 3000$
• زیرمسئله چهارم (۱۴ نمره): $p_i = i-1$
• زیرمسئله پنجم (۵۲ نمره): بدون محدودیت اضافی

• $1\leq n\leq 10^{5}$
• $1\leq m\leq 3\times 10^{5}$
• $1\leq p_i < i$
• $1\leq u,v \leq n$, $u\neq v$
• $v$ ارشد $u$ است.
• $1\leq c\leq 10^{9}$

در ورودی نمونه‌ی اول، در صورت برگزاری مهمانی اول، کارمندان $1$، $2$ و $3$، در صورت برگزاری مهمانی دوم، کارمندان $1$، $2$ و $4$ و در صورت برگزاری مهمانی سوم، کارمندان $2$ و $4$، در این مهمانی‌ها حضور خواهند داشت. در سه حالت زیر، شرط شرکت مبنی بر این‌که هر کارمند (به جز مدیر عامل) باید با مسئولش در حداقل یک مهمانی شرکت کند، برقرار است:

• مهمانی‌های $1$ و $2$ برگزار شوند: در این صورت هزینه‌ی مهمانی‌ها برابر است با $10+20=30$.
• مهمانی‌های $1$ و $3$ برگزار شوند: در این صورت هزینه ی مهمانی‌‌ها برابر است با $10+15=25$.
• مهمانی‌های $1$، $2$ و $3$ برگزار شوند: در این صورت هزینه‌ی مهمانی‌ها برابر است با $10+20+15=45$.

بنابراین کم‌ترین هزینه برابر با $25$ تومان است.

• سوال قبل