题目描述

在皇家婚礼后，$Jiajia$和$Wind$隐居在$XX$村庄，过着平凡的幸福生活。$XX$村庄的居民住在美丽的小屋中，某些小屋之间通过双向道路连接。我们称直接相连的小屋为"直接连接"。$XX$村庄的特殊之处在于：从任意小屋出发都能到达其他所有小屋，且若每条道路只能走一次，则任意两小屋间的路径是唯一的。

由于$Jiajia$赚够了钱，$Wind$成为家庭主妇。他们的孩子喜欢去其他孩子家玩，然后给$Wind$打电话："妈妈，接我回家！"

在不同时间段，行走道路所需时间可能不同。例如：$Wind$正常情况下走某条路需要$5$分钟，但若路上有可爱的小狗可能要$10$分钟，若有奇怪气味可能只需$3$分钟。

$Wind$深爱孩子们，因此希望准确告知孩子们行走道路所需时间。你能帮助她吗？

输入

第一行包含三个整数$n$、$q$、$s$，分别表示$XX$村庄的小屋数量、待处理消息数量，以及$Wind$当前所在小屋编号。保证$n<100001$，$q<100001$。

接下来的$n-1$行，每行包含三个整数$a$、$b$、$w$，表示小屋$a$和$b$之间有直接道路，初始时间为$w$（$1 \leq w \leq 10000$）。

接下来的$q$行，每行是以下两种消息之一：

• 消息$A$：$0$ $u$
  表示小屋$u$的孩子呼叫Wind，她需从当前位置前往小屋$u$
• 消息$B$：$1$ $i$ $w$
  表示将第$i$条道路的时间修改为$w$（修改仅发生在$Wind$静止等待时）

输出

对每个消息$A$，输出一个整数$X$，表示接孩子所需时间。

样例输入

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

样例输出

1  
3  

来源

POJ Monthly--2006.02.26, zgl & twb