有左右两排各 $$$n$$$ 个共 $$$2n$$$ 个点，点从 $$$1$$$ 到 $$$2n$$$ 编号，左边一排为 $$$1$$$ 到 $$$n$$$，右边一排为 $$$n+1$$$ 到 $$$2n$$$。

最开始有 $$$n$$$ 条有向边，第 $$$i$$$ 条边由 $$$i$$$ 指向 $$$i+n$$$，经过这些有向边你不需要花费时间。同时有 $$$2n-2$$$ 条无向边，第 $$$i$$$ 条连接 $$$u_i$$$ 和 $$$v_i$$$，通行需要花费 $$$w_i$$$ 的时间。

为了让这个图尽可能美观，保证不会有一条无向边横跨左右。并且有且仅有 $$$n-1$$$ 条无向边满足 $$$u_i,v_i$$$ 均为左边一排的节点。同时，保证左右两排排内的点相互连通。

你可以从一个点开始旅行，当你停留在点上时你可以选择通过一条有向出边或无向边走到相邻节点，当然你需要花费边所对应的时间。同时，你不会重复经过一条边，这是件无趣的事情。

接下来有 $$$q$$$ 个问题需要你回答，每次你需要计算在从 $$$x_i$$$ 旅游至 $$$y_i$$$ 你所能旅行的最大时间。在点上停留的时间可以忽略不计。同时你需要保证你在任意时刻都存在一条满足要求的到达 $$$y_i$$$ 的旅行路线。保证一定存在一条有限时间内的从 $$$x_i$$$ 到 $$$y_i$$$ 的路线。