本题的故事发生在 SPFA 之都，在这里我们将为你介绍一些必要的设定。

SPFA 之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$）。我们依次用 $l,a$ 描述一条边的长度、卡常程度。

作为死了的代表城市，SPFA 之都时常有被卡的消息传出，因此 NOI 掉分总是不可避免的。由于出题人知道整个城市所有人的 SPFA 水平，因此会被卡的代码一定是代码强度相对最低的一些边。我们用出题人的毒瘤程度来描述卡常的程度，它的意义是：所有代码强度不超过毒瘤程度的代码都是会被卡的。

Yazid 是一名来自 SPFA 之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在 SPFA 之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的出题人的毒瘤程度 $p$。

每一天，Yazid 在出发点都拥有一份 SPFA 代码。这份代码因为容易被卡不能经过有设置卡常的边。Yazid 可以在任意节点放弃代码，这样接下来他就可以使用 dijkstra 通过有卡常的边。但代码会被留在他放弃的节点并不会再被使用。

需要特殊说明的是，第二天代码会被重置，这意味着：

• 代码会在新的出发点被准备好。
• Yazid 不能利用之前在某处放弃的代码。

Yazid 非常讨厌写 dijkstra，因此他希望在完成回家这一目标的同时，最小化他写 dijkstra 经过的边的总长度。请你帮助 Yazid 进行计算。