U442117 [USACO Oct08]牧场旅行

GXYZOJ P317

$n$ 个被自然地编号为 $1\dots n$ 奶牛 正在同样被方便的编号为 $1\dots 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$ 。 通道只会连接两个不同的牧场，所以这些通道使得整个牧场构成了一棵树。 奶牛们是好交际的，所以希望能够经常的访问别的奶牛。急切地，它们希望你能通过告诉它们 $Q$ 对牧场的路径来帮助他们安排旅行。$($ 这里将有Q个询问， $p1,p2(1\le p1 \le n,1 \le p1\le n))$

第 $1$ 行：两个用空格隔开的整数：$n$ 和 $Q$ 第 $2\dots n$ 行：第 $i+1$ 行包含三个用空格隔开的整数：$A_i$ ， $B_i$ 和 $L_i$ 第 $n+1\dots N+Q$ 行：每行包含两个用空格隔开的整数，代表两个不同的牧场，$p1$ 和 $p2$

第 $1\dots Q$ 行：第 $i$ 行包含第 $i$ 个询问的答案。

$(1\le n\le1000)$ $(1\le L_i \le10000)$ $(1\le Q\le1000）$