说明

$X$村的人们住在美丽的小屋里。若两个小屋通过双向道路连接，则可以说这两个小屋直接相连。$X$村非常特别，可以从任意小屋到达任意其他小屋，每两个小屋之间的路线都是唯一的。

温迪的子节点喜欢去找其他子节点玩，然后打电话给温迪：“妈咪，带我回家！”。在不同的时间沿道路行走所需的时间可能不同。温迪想告诉她的子节点她将在路上花的确切时间。

输入

第$1$行包含$3$个整数$n$ 、$q$ 、$s$ ，表示有$n$ 个小屋、$q$ 个消息，温迪目前在$s$ 小屋里，$n$ $<$$1$$0$$0$$0$$0$$1$，$q$$<$$1$$0$$0$$0$$0$$1$。

以下$n$ -$1$行各包含$3$个整数$a$、$b$ 和$w$ ，表示有一条连接小屋$a$ 和$b$ 的道路，所需的时间是$w$ （$1$$≤$$w$ ≤$1$$0$$0$$0$$0$）。

以下$q$ 行有两种消息类型：

①消息$A$，即$0$ $u$，子节点在小屋$u$ 中给温迪打电话，温迪应该从现在的位置去小屋$u$ ；

②消息$B$，即$1$ $i$ $w$ ，将第$i$ 条道路所需的时间修改为$w$ （注意：温迪在途中时，时间不会发生改变，时间在温迪停留在某个地方等待子节点时才会改变）。

输出

对每条消息$A$，都输出一个整数，即找到子节点所需的时间。

样例

3 3 1
1 2 1
2 3 20
0 2
1 2 3
0 3

1
3

来源

POJ2763