U313893 彩虹桥

洛基又逃走了！索尔被迫又走上了追捕弟弟的道路。 这次洛基逃到了 M78-58 星，这里地形险恶，共有 $N$ 个城市编号 $1 \sim N$，城市之间有 $M$ 条路，没有路的地方连索尔也走不了！ 索尔在 $S$ 城落地，之后会发生 $2$ 类事件： 第一类是洛基对尚未被施咒的城市 $x$ 施咒，使得索尔在此以后再也不能经过或进入城市 $x$（自己也很蠢地被关在外面）； 第二类是索尔接到神盾局消息洛基在 $x$ 城出现，索尔需要从当前城市赶到 $x$ 城，在下一次二类事件发生前他会呆在 $x$ 城（保证索尔当前在的城市和要去的城市均未被施咒）。 索尔想知道，他每次要赶到 $x$ 城最少要走多长的路。如果没有路，他会用彩虹桥将自己穿送到 $x$ 城，但是由于彩虹桥每次耗费的黑暗能量太多，如非必要他不会使用。 现在索尔想知道，每次出现第二类事件他最少要走多少路，如果没办法走到他就用彩虹桥，输出`-1`；否则输出最短路程。

第一行 $5$ 个整数 $N,M,S,D,B$，$D$ 表示一类事件的总数，$B$ 表示二类事件的总数。 接下来 $M$ 行，每行 $3$ 个整数 $Y,Z,L$，表示 $Y$ 和 $Z$ 之间有一条长度为$L$的路。 接下来 $D+B$ 行，每行 $1$ 个小写字母和 $1$ 个整数 $x$，表示一个事件，如果字母是`d`，表示洛基对城市 $x$ 施咒；如果字母是`b`，表示索尔要赶到城市 $x$。

输出 $B$ 行，对于每个二类事件输出对应的答案。

对于 $30\%$ 的数据，有 $2 \le N \le 50$。 对于另外 $30\%$ 的数据，有 $0 \le B \le 100$。 对于 $100\%$ 的数据，有 $1 \le N \le 300, 1 \le M \le 10^5, 0 \le D < N, 1 \le L \le 10^6, 1 \le B \le 5*10^5$。