# شرکت بروبچ و شرکا time limit per test: 3 seconds memory limit per test: 128 megabytes ---------- شرکت ساختمانی بروبچ و شرکا، از کنار هم جمع شدن تعدادی دوست تشکیل شده که هر روز صبح اول وقت هر کدام با وانت خود به محل کار مشترک که یک ساختمان در حال تکمیل است، و با نام «ساختمون» شناخته می‌شود، می‌روند. اخیراً بروبچ با دو مشکل جدید مواجه شده‌اند. اولین مشکل از زمانی پیش آمده که سهمیه‌بندی سوخت شروع شد، بروبچ به این نتیجه رسیدند که برای کاهش مصرف سوخت بهتر است از یک وانت برای انتقال چند نفر استفاده کنند. مثلاً ممکن است چند نفر از بروبچ با وانت خود به منزل یکی بروند، آنجا وانت خود را پارک کنند و همه با یکی از وانت‌ها به ساختمون بروند. همچنین همسایگان ساختمون از شلوغی زیاد اطراف ساختمون و پیدا نشدن جای پارک شکایت کرده‌اند و بروبچ در پارک کردن وانت خود در اطراف ساختمون دچار مشکل شده‌اند. شما باید به آن‌ها کمک کنید تا بهترین روش برای رفتن به ساختمون را با کمترین میزان مصرف سوخت پیدا کنند. فرض بر این است که میزان مصرف سوخت متناسب است با میزان مسافتی که ماشین‌ها طی می‌کنند. همچنین وانتی که در ساختمون پارک کند تا پایان روز همان‌جا باقی می‌ماند. ## ورودی ورودی شامل یک مورد تست است. در خط اول عدد صحیح $n$ که تعداد راه‌های ارتباطی ممکن برای جابه‌جایی آمده است. $n$ خط بعدی هر یک اطلاعات مربوط به یکی از راه‌های ارتباطی است که شامل دو نام و یک عدد صحیح مثبت است. نام‌ها یا نام دو نفر از بروبچ یا کلمه Sakhtemoon است و عدد صحیح فاصله بین آن‌ها است. راه‌ها دو طرفه فرض می‌شود. حداکثر اعضای بروبچ ۲۰ نفر و حداکثر طول نام هر یک ۱۰ است. در خط انتهایی عدد صحیح $s$ که حداکثر تعداد ماشین‌هایی است که می‌توانند در نزدیکی ساختمون پارک شوند. می‌توانید فرض کنید از منزل هر یک از اعضای بروبچ به ساختمون مسیری وجود دارد و مسأله جواب دارد. ## خروجی خروجی از یک خط تشکیل شده و در آن جمع مسافتی که وانت‌ها طی می‌کنند می‌آید. ## مثال ورودی 10 A B 32 A Sakhtemoon 57 A D 43 B Sakhtemoon 19 B C 82 C Sakhtemoon 65 C E 90 C D 109 Sakhtemoon E 24 E D 79 3 خروجی 183 ورودی 10 A B 32 A Sakhtemoon 57 A D 43 B Sakhtemoon 19 B C 82 C Sakhtemoon 65 C E 90 C D 109 Sakhtemoon E 24 E D 79 1 خروجی 255