الأبقار $N$ ($2 \le N \le 1,000$) مرقمة بسهولة $1,\ldots,N$ وترعى في $N$ مراعي مرقمة كذلك. والأيسر أن البقرة $i$ في المرعى $i$.

تربط $N-1$ ممرات ثنائية الاتجاه بعض الأزواج. الممر $i$ يربط $A_{i}$ و$B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$)، طوله $L_{i}$ ($1 \le L_{i} \le 10,000$).

بين أي مرعيين مختلفين طريق واحد بالضبط، فتشكل الممرات شجرة.

الأبقار اجتماعية وتريد زيارات كثيرة وهي دائمًا مستعجلة. ساعد في التخطيط بحساب أطوال الطرق لـ$Q$ أزواج ($1 \le Q \le 1,000$)، كل استعلام $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

الإدخال

• السطر 1: عددان صحيحان بمسافة $N$ و$Q$.
• الأسطر $2,\ldots,N$: السطر $i+1$ يحتوي ثلاثة أعداد صحيحة بمسافات $A_{i}$ و$B_{i}$ و$L_{i}$.
• الأسطر $N+1,\ldots,N+Q$: عددان صحيحان بمسافة $p1$ و$p2$ لمرعيين مختلفين يراد السفر بينهما.

الإخراج

• الأسطر $1,\ldots,Q$: السطر $i$ يحتوي طول طريق الاستعلام $i$.

أمثلة

الإدخال 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

الإخراج 1

2
7

ملاحظة

الاستعلام 1: طول ممر 1–2 هو 2. الاستعلام 2: ممر 3–4 ثم 4–1 ثم 1–2، المجموع 7.

المهام الفرعية

النقاط: 200

نسبة المسألة: Neal Wu, 2007