#2524. 家庭主妇

家庭主妇

说明

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

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

输入

11行包含33个整数nnqqss ,表示有nn 个小屋、qq 个消息,温迪目前在ss 小屋里,nn <<110000000011qq<<110000000011

以下nn -11行各包含33个整数aabbww ,表示有一条连接小屋aabb 的道路,所需的时间是ww11ww1100000000)。

以下qq 行有两种消息类型:

①消息AA,即00 uu,子节点在小屋uu 中给温迪打电话,温迪应该从现在的位置去小屋uu

②消息BB,即11 ii ww ,将第ii 条道路所需的时间修改为ww (注意:温迪在途中时,时间不会发生改变,时间在温迪停留在某个地方等待子节点时才会改变)。

输出

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

样例

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

来源

POJ2763