رژیم غذایی

تعدادی از شاگردان باشگاه آقا داوود، برنامه‌ی غذایی خود را برای این ماه به دلیل آماده نبودن، دریافت نکرده‌اند. اکنون این برنامه‌ها آماده شده است و آقا داوود تصمیم گرفته آن‌ها را به صورت حضوری به شاگردانش برساند. می‌دانیم شهر سکونت آقا داوود شامل $N$ تقاطع است که این تقاطع‌ها با $M$ جاده‌ی دوطرفه به هم متصل شده‌اند. برای عبور از جاده‌ها، افراد باید سوار اتوبوس شوند و نمی‌توانند در بین راه از اتوبوس پیاده شوند. آقا داوود با شاگردانش تماس گرفته و محل فعلی آن‌ها را می‌داند. حال آن‌ها قصد دارند طوری از اتوبوس‌ها استفاده کنند که در کمترین زمان ممکن همه دارای برنامه غذایی باشند. یک فرد زمانی می‌تواند به برنامه غذایی خود برسد که در یک زمان با آقا داوود در یک ایستگاه باشد. دقت کنید که افراد می‌توانند در ایستگاه‌ها منتظر بمانند. برای فهم کامل شرایط مسئله توصیه می‌شود به ورودی و خروجی نمونه و توضیحات آنها دقت کنید. می‌دانیم آقا داوود در تقاطع شماره ۱ است و با استفاده از اتوبوس‌ها می‌توان از هر تقاطعی به هر تقاطع دیگری رفت.

• خط اول ورودی شامل 2 عدد صحیح $N$ تعداد تقاطع‌ها و $M$ تعداد جاده‌ها است $1\leq N, M \leq 2000$ .
• خط‌های 2 تا $M+1$ام هر کدام شامل ۳ عدد صحیح $U, V$ و $W$ است، به این معنا که بین تقاطع‌های $U$ و $V$ جاده‌ای داریم که عبور از آن $W$ ثانیه طول می‌کشد. تضمین می‌شود که بین هر جفت از تقاطع‌ها حداکثر یک جاده‌ی دوطرفه است ($1 \leq U, V \leq N, U \neq V, 1 \leq W \leq 100000$).
• خط $M+2$ام شامل عدد صحیح $K$، تعداد شاگردان، است ($1 \leq K \leq N-1$).
• خط بعد شامل $K$ عدد صحیح و متمایز $p_1,p_2, \cdots,p_k$ است به طوری که $p_i$ مکان ابتدایی شاگرد $i$ام را نشان می‌دهد ($1 < p_1, \cdots, p_k \leq N$).
• در ۵۰ درصد از ورودی‌ها $1 \leq M \leq 2000$ و $ 1 \leq K < N \leq 300$ است.

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

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

• در ورودی اول اگر آقا داوود و شاگردانش اتوبوس متصل از جایگاه فعلی خود به تقاطع شماره ۴ را سوار شوند، بعد از یک ثانیه هر دو شاگرد به آقا داوود می‌رسند و برنامه‌ی غذایی خود را دریافت می‌کنند.
• در ورودی دوم، اگر شاگرد اول اتوبوس بین تقاطع های ۲ و ۳ را سوار شود، شاگرد دوم اتوبوس بین تقاطع های ۳ و ۴ را سوار شود و آقا داوود ابتدا اتوبوس بین تقاطع های ۱ و ۲ و سپس بین تقاطع‌های ۲ و ۳ را سوار شود، در این صورت شاگرد اول بعد از ۵ ثانیه انتظار برای آقا داوود - ثانیه ۱۰ ام- در تقاطع ۲ به برنامه خود می‌رسد و شاگرد دوم با ۱ ثانیه تاخیر نسبت به آقا داوود - ثانیه ۱۶ ام - در تقاطع ۳ به برنامه خود می‌رسد.

• سوال قبل