2023 年上海市大学生程序设计竞赛 - 一月赛

输入格式

The first line of input contains a positive integer $n$ ($1\le n\le 1\times {10}^5$) , indicating the number of classrooms in the teaching building.

The next $n-1$ line has three integers $u,v,w$ in each line, indicating that there is a passage between classroom $u$ and classroom $v$ , and lbromine needs $w$ seconds to pass through the passage $(1\le u,v\le n,1\le w\le {10}^9)$

An integer $q$ in line $n+1$ represents the number of queries $(1\le q\le 1\times {10}^4)$

The next $q$ line has two integers $l,r$ per line,indicating the query interval $(1\le l<r\le n)$

输出格式

For each query output one line contains one integer indicating the shortest possible time for him to find Komorebi and Amuzi.

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

6
2
7

提示

The structure of the teaching building in the sample is as follows

So for the interval $[1,3]$ ,if Komorebi hides in classroom $1$ and Amuzi hides in classroom $2$,lbromine can transmit to classroom $1$ and go through classroom $5$ and $4$ to classroom $2$ using $6$ secends.It can be proved that this is the shortest possible time for lbromine to find Komorebi and Amuzi.