هیئت مدیره‌ی شرکت الفبا، برای افزایش صمیمیت بین کارمندانش، تصمیم به برگزاری تعدادی مهمانی گرفته است. می‌دانیم که در این شرکت، هر فرد (به جز مدیرعامل) دقیقا یک مسئول دارد. هم‌چنین کارمند $x$ را ارشد کارمند $y$ می‌گوییم اگر حداقل یکی از دو شرط زیر برقرار باشد:
این شرکت قصد دارد تعدادی مهمانی برگزار کند که در آن‌ها هر فرد (به جز مدیر عامل) با مسئولش، حداقل در یک مهمانی حضور داشته باشند. با توجه به سیاست‌های شرکت، تنها $m$ مهمانی قابل برگزاری است که هر کدام از آن‌ها را می‌توان با سه تایی $(u,v,c)$ نمایش داد. معنای این سه‌تایی این است که هزینه‌ی برگزاری مهمانی برابر با $c$ تومان است و افرادی
هم‌چنین می‌دانیم که در هر مهمانی مانند $(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)$ است.
در تنها سطر خروجی کمترین هزینه برای رسیدن به خواسته‌ی شرکت را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 4 3 1 2 2 3 1 10 4 1 20 4 2 15 | 25 |
در ورودی نمونه‌ی اول، در صورت برگزاری مهمانی اول، کارمندان $1$، $2$ و $3$، در صورت برگزاری مهمانی دوم، کارمندان $1$، $2$ و $4$ و در صورت برگزاری مهمانی سوم، کارمندان $2$ و $4$، در این مهمانیها حضور خواهند داشت. در سه حالت زیر، شرط شرکت مبنی بر این‌که هر کارمند (به جز مدیر عامل) باید با مسئولش در حداقل یک مهمانی شرکت کند، برقرار است:
بنابراین کمترین هزینه برابر با $25$ تومان است.