+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- یک روز یک خری متعلق به مناطق بیابانی به کازابلانکا رفت درحالیکه به دلیل خرارت(خر بودن) فکر می‌کرد که به کارخانه‌ی شکلات سازی ویلی ونکا رفته‌است! خر داستان ما تنها یک بار کتاب "چارلی و کارخانه‌ی شکلات‌سازی" را خورده است و خیلی جزییات داستان را به یاد ندارد. به همین دلیل او نمی‌تواند کازابلانکا و این کارخانه‌ را از هم تشخیص دهد. اما حقیقت این است که واقعا تفاوت خیلی زیادی بین این دو وجود ندارد! برای مثال هر دو را می‌توان به شکل محدوده‌ای با $n$ میدان تصور کرد که با $n - 1$ جاده به هم متصل شده‌اند، بصورتی که می‌توان با گذر از تعدادی جاده از هر میدان به هر میدان دیگری سفر کرد. (یعنی ساختار گراف میادین و جاده‌ها یک درخت است.) در کارخانه‌ی شکلات سازی، این جاده‌ها همگی از شکلات هستند و خر می‌تواند هنگام گذر از جاده‌ها شکلات آن‌ را بخورد. خر ابتدا از شکلات هر جاده (که در واقع گل‌های کف جاده‌های کازابلانکا هستند) یک مقدار تست کرده‌است و برای هر جاده می‌داند که شکلات کف آن جاده چه مقدار خوش‌مزه است. خر پس از جمع کردن این اطلاعات، یک نقشه‌ی جامع تهیه کرد که در آن جاده‌های موجود و خوش‌مزگی شکلات کف هر جاده مشخص شده بود. برخی از این مقادیر خوش‌مزگی منفی بودند که یعنی خر از مزه‌ی شکلات آن خوشش نمی‌آید. (خر کمی به این موضوع شک می‌کند چون او همه‌ی شکلات‌ها را دوست داشت، اما مطالعات اخیر او پیرامون نوشته‌های *جان استوارت میل* این که اکنون از برخی شکلات‌ها خوشش نمی‌آید را توجیه می‌کرد.) حال این خر در حال برنامه‌ریزی یک سفر رویایی در این کارخانه‌‌ی اسرارآمیز است. سفر مدنظر خر از یکی از میادین شروع می‌شود و در یک میدان پایان می‌یابد. خر در این سفر مسیر بین این دو میدان را طی می‌کند. (دقت کنید که با توجه به ساختار درختی نقشه، چنین مسیری یکتا است.) همه می‌دانند که خر داستان ما خریست که زمان برایش بسیار مهم است (بدلیل دغدغه‌های کاری) و نمی‌خواهد وقتش تلف شود؛ پس برنامه‌اش را طوری می‌چیند که حتما تعدادی (که ممکن است برابر ۰ باشد) از جاده‌های ابتدای مسیر و یا انتهای مسیر را چهارنعل حرکت کند و شکلات روی جاده‌های این بین (که آن جاده‌ها را چهارنعل نمی‌رود) را بخورد. یعنی به عبارتی یک بازه‌ی پشت سرهم از جاده‌های مسیر را انتخاب می‌کند که شکلات‌هایشان را بخورد و پیش از رسیدن به این بازه و پس از آن را چهار نعل می‌رود. لذتی که او از خوردن این شکلات‌ها می‌برد برابر مجموع خوش‌مزگی آن‌هاست. حال خر بدلیل ضیق وقت به سراغ شما، از بهترین برنامه‌نویسان جهان، آمده‌است تا از شما تعدادی سوال راجع به برنامه‌ریزی سفرش بپرسد. او ابتدا نقشه‌ی کارخانه‌ی شکلات‌سازی را به شما می‌دهد و سپس $q$ سوال به این شکل از شما می‌پرسد: اگر او بخواهد از میدان $u$ به میدان $v$ سفر کند، بیشترین میزان لذتی که می‌تواند از خوردن شکلات‌ها ببرد چقدر است؟ (دقت کنید که این مقدار همیشه نامنفی است؛ زیرا خر می‌تواند بدون خوردن هیچ شکلاتی با ۰ لذت این مسیر را بپیماید.) # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $q$ آمده‌است که به ترتیب نمایانگر تعداد میادین در کار‌خانه‌ی شکلات سازی (یا همان کازابلانکای واقعی!) و تعداد پرسش‌های خر است. میدان‌های کارخانه با اعداد طبیعی ۱ و ۲ و ... و $n$ شماره‌گذاری شده‌اند. $$1 \le n, q \le 100\ 000$$ سپس در $n - 1$ سطر بعدی توصیف نقشه‌ی تهیه‌شده توسط خر آمده‌است؛ در هریک از این $n - 1$ سطر سه عدد $u$ و $v$ و $d$ آمده‌است که نمایانگر وجود یک جاده بین میادین $u$ و $v$ با میزان خوش‌مزگی شکلات $d$ است. $$1 \le u, v \le n$$ $$u \neq v$$ $$|d| \le 10^9$$ سپس در هریک از $q$ سطر بعدی، دو عدد طبیعی $x$ و $y$ آمده‌است که نمایانگر شماره میدان دو سر مسیر مورد پرسش خر می‌باشد. $$1 \le x, y \le n$$ # خروجی خروجی باید شامل $q$ سطر باشد که هریک شامل تنها یک عدد است. عدد موجود در $i$امین سطر آن خروجی باید نمایانگر پاسخ $i$امین سوال خر باشد. # مثال ## ورودی نمونه ``` 7 9 1 2 -4 5 4 -2 5 1 10 2 7 8 3 6 7 7 6 9 7 1 1 2 4 3 5 5 3 4 5 7 7 5 1 1 3 7 ``` ## خروجی نمونه ``` 8 0 30 0 30 14 14 0 16 ```