یک گروه موسیقی ناشناخته می‌خواهد برای کسب شهرت در همه‌ی شهر‌های کشور خود کنسرت برگزار کند. مانند خیلی از کشور‌ها ساختار جاده‌های این کشور نیز یک گراف درخت می‌باشد و شهرها از $1$ تا $n$ شماره‌گذاری شده‌اند. به این معنی که شهر‌های این کشور با تعدادی جاده‌ی دو طرفه به هم متصل شده‌اند به گونه‌ای که مسیر بین هر دو شهر یکتا می‌باشد. با توجه به هزینه‌های سفر و اشتیاق اعضای گروه برای ثروتمند شدن، تصمیم گروه بر آن شده است که در انتهای سفر‌شان بیشترین سود ممکن را به دست آورند.
سفر گروه موسیقی از یک شهر دلخواه شروع می‌شود. گروه هر بار با سفر از طریق یکی از جاده‌های مجاور شهر فعلی به شهری مجاور می‌رود. گروه موسیقی هنگامی که برای اولین بار وارد شهر $i$ می‌شود، با برگزاری یک کنسرت موسیقی در آن شهر به مقدار $C_i$ واحد سود می‌کند. هم‌چنین برای هربار عبور از جاده‌ی بین دو شهر باید هزینه‌ی سفر در آن جاده را پرداخت کند. سفر در هر جاده هزینه‌ی به‌خصوصی دارد.
گروه موسیقی سفر خود را از یک شهر دلخواه آغاز می‌کند و با اجرای کنسرت در شهر آغازین مقداری پول برای ادامه‌ی سفر خود به دست می‌آورد. گروه به همه شهرها سفر می‌کند و در نهایت به شهر اولیه‌ی خود باز می‌گردد. برای عبور از یک جاده گروه باید به اندازه‌ی هزینه‌ی سفر در آن جاده پول داشته باشد، به این معنا که در طول سفر هیچ گاه نباید خرج گروه از دخلش بیشتر شود. به گروه کمک کنید و حساب کنید که بیشترین سودی که می‌توان با انجام این برنامه به‌دست آورد چه‌قدر می‌باشد.