G. 企鹅物流の礼物

众所周知，企鹅物流是龙门的一家正经的物流运输公司。

龙门一共有 家住户，这 家住户通过 条道路连接形成一个无向图 。

正值愚人节这几天，企鹅物流的老板 大帝为了庆祝他的演唱会顺利进行，准备每天给龙门的每一位住户发放企鹅物流的精美小礼品，这可把德克萨斯愁坏了，这么多的礼物怎么送的完。

但是幸运的是，龙门这几天开交通管制，每条边有一个权值 , 只有重量 的货可以通过。这可把德克萨斯高兴坏了，这下子他可以摸鱼了。

龙门人非常的慷慨，虽然是免费送的小礼品，但是他们会回报 的小费，德克萨斯想得到尽可能多的小费。

总的来说，一共有 天要送货，每天从点 出发开始送重量为 的货，只能经过 的边，经过一个点就可以得到 的小费，问每天最多能得到多少小费。

第一行三个数 ,,。

第二行 个数，第 个数为 。

接下来 行，每行三个数 ,,,表示从 到 有一条权值为 的边。

接下来 行，每行两个数 ,，表示每天送货的起始地点，送货重量。

对于每组询问，输出一个整数表示每天最多能得到多少小费。

样例输入

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5
1 1
6 2
8 9

样例输出

3
55
55
25

,