$N$ Kühe ($2 \le N \le 1,000$), bequem nummeriert $1,\ldots,N$, grasen auf ebenso nummerierten $N$ Weiden. Am bequemsten: Kuh $i$ ist auf Weide $i$.

$N-1$ bidirektionale Wege verbinden einige Paare. Weg $i$ verbindet $A_{i}$ und $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), Länge $L_{i}$ ($1 \le L_{i} \le 10,000$).

Zwischen verschiedenen Weiden gibt es genau einen Pfad, also bilden die Wege einen Baum.

Die geselligen Kühe wollen häufig Besuche machen und haben immer Eile. Hilf beim Planen mit Pfadlängen für $Q$ Paare ($1 \le Q \le 1,000$), Anfragen $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Eingabe

• Zeile 1: ganze Zahlen $N$, $Q$ mit Leerzeichen.
• Zeilen $2,\ldots,N$: Zeile $i+1$ enthält drei ganze Zahlen mit Leerzeichen $A_{i}$, $B_{i}$, $L_{i}$.
• Zeilen $N+1,\ldots,N+Q$: zwei ganze Zahlen mit Leerzeichen $p1$, $p2$, verschiedene Reiseweiden.

Ausgabe

• Zeilen $1,\ldots,Q$: Zeile $i$ gibt die Pfadlänge der Anfrage $i$.

Beispiele

Eingabe 1

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

Ausgabe 1

2
7

Hinweis

Anfrage 1: Weg 1–2 hat Länge 2. Anfrage 2: 3–4, dann 4–1, schließlich 1–2 ergibt 7.

Teilaufgaben

Punkte: 200

Aufgabenautor: Neal Wu, 2007