$N$ vaches ($2 \le N \le 1,000$), commodément numérotées $1,\ldots,N$, paissent dans $N$ pâturages numérotés de même. Encore mieux, la vache $i$ est au pâturage $i$.

$N-1$ sentiers bidirectionnels relient certaines paires. Le sentier $i$ relie $A_{i}$ à $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), longueur $L_{i}$ ($1 \le L_{i} \le 10,000$).

Toute paire distincte a exactement un chemin, donc les sentiers forment un arbre.

Sociables et toujours pressées, les vaches veulent souvent se visiter. Aidez à organiser ces visites en calculant les longueurs pour $Q$ paires ($1 \le Q \le 1,000$), requêtes $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Entrée

• Ligne 1 : entiers $N$, $Q$ séparés par un espace.
• Lignes $2,\ldots,N$ : la ligne $i+1$ contient trois entiers séparés par des espaces $A_{i}$, $B_{i}$, $L_{i}$.
• Lignes $N+1,\ldots,N+Q$ : deux entiers séparés par un espace $p1$, $p2$, pâturages distincts à visiter.

Sortie

• Lignes $1,\ldots,Q$ : la ligne $i$ donne la longueur du chemin de la requête $i$.

Exemples

Entrée 1

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

Sortie 1

2
7

Remarque

Requête 1 : le sentier 1–2 mesure 2. Requête 2 : prendre 3–4, puis 4–1, enfin 1–2, total 7.

Sous-tâches

Points : 200

Crédits du problème : Neal Wu, 2007