Background

大卫为了救露西葬身荒坂。法尔科要完成大卫的嘱托，带露西逃离。

Description

法尔科可能会去到 个地点，共有 条路将其联通，每条路都是双向联通的。露西通过黑客技术得到了信息，荒坂公司为了抓捕他们，在这 条路上设置了不同程度的拦截 。法尔科的车是有耐久的，不可能随便冲关。具体来说，法尔科每经过一条路，其车的耐久就会减少该路对应的 。法尔科车子的耐久上限为 。这样子可能很难冲出重围，所以法尔科提前联系好了 个地点的维修商（ 到 ），到达该地点后，车子的耐久度恢复至上限 。 现在请你帮帮法尔科，他有 次询问，问从维修站 到达维修站 所需要的最小 。

输入格式

第一行给定四个整数 。 接下来 行，每行三个整数， 表示 与 之间有一条拦截程度为 的路。 接下来 行，每行两个整数 表示询问的地点。保证 不等于 ，且

输出格式

输出 行，每行一个整数 ,表示该次询问能够到达所需的最小 。

样例

9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3

38
15

数据范围