题意：

给定一张包含 $n$ 个点、$m$ 条有向边的有向无环图（DAG）。每条边均有一个非负整数边权，并指定一个终点 $t$。

保证从任意节点出发，都至少存在一条有向路径能够到达终点 $t$。

每个节点具有一个状态，由长度为 $n$ 的 $01$ 字符串 $S$ 给出，其中 $S_i$ 表示节点 $i$ 的状态。

旅行者当前位于节点 $u\neq t$ 时，根据 $S_u$ 按照以下规则选择一条出边：

• 若 $S_u=0$，旅行者从节点 $u$ 的所有出边中等概率随机选择一条。
• 若 $S_u=1$，旅行者从所有 $u\to t$ 的最短路径中等概率随机选择一条，并沿该路径的第一条边移动。

更具体地，设从 $u$ 到 $t$ 的最短路径共有 $K_u$ 条。对于一条具体的出边 $e=(u,v)$，设以边 $e$ 作为第一条边的 $u\to t$ 最短路径共有 $C_e$ 条，则选择边 $e$ 的概率为

$$\frac{C_e}{K_u}.$$

若一条出边不属于任何 $u\to t$ 的最短路径，则其被选择的概率为 $0$。

路径按照经过的边序列区分，因此即使存在端点相同的多条边，它们也视为不同的边。

旅行者沿一条权值为 $w$ 的边移动时，本次移动产生 $w$ 的距离。一旦到达终点 $t$，移动立即结束。特别地，从 $t$ 出发到达 $t$ 的期望总距离为 $0$。

对于每个节点 $i$，求从节点 $i$ 出发最终到达终点 $t$ 时，所经过边的权值之和的期望值。

答案对 $998244353$ 取模。

对于有理数 $\frac{a}{b}$，其模 $998244353$ 的值定义为

$$a\cdot b^{-1}\pmod{998244353},$$

其中 $b^{-1}$ 表示 $b$ 在模 $998244353$ 意义下的乘法逆元。

输入格式：

第一行输入三个整数 $n,m,t$（$1\le n\le 2\times 10^5$，$0\le m\le 4\times 10^5$，$1\le t\le n$），分别表示节点数、边数和终点编号。

第二行输入一个长度为 $n$ 的字符串 $S$（$|S|=n$，$S_i\in\{\texttt{0},\texttt{1}\}$），其中 $S_i$ 表示节点 $i$ 的状态。

接下来 $m$ 行，每行输入三个整数 $u,v,w$（$1\le u,v\le n$，$0\le w\le 10^9$），表示一条从节点 $u$ 指向节点 $v$、边权为 $w$ 的有向边。

保证给出的图为有向无环图，并且每个节点都至少存在一条到达终点 $t$ 的有向路径。

对于所有满足 $u\neq t$ 且 $S_u=1$ 的节点 $u$，保证从 $u$ 到 $t$ 的最短路径条数 $K_u$ 不被 $998244353$ 整除。

输出格式：

输出一行 $n$ 个整数，第 $i$ 个整数表示从节点 $i$ 出发到达终点 $t$ 时，经过边的权值之和的期望值对 $998244353$ 取模后的结果。

样例：

样例输入：

5 6 5
10110
1 2 1
1 3 2
2 4 1
2 5 2
3 5 1
4 5 1

样例输出：

3 2 1 1 0

样例解释：

记从节点 $u$ 出发到达终点 $5$ 的期望总距离为 $E_u$。

节点 $5$ 为终点，因此 $E_5=0$。

节点 $4$ 的状态为 1，且只有一条出边 $(4,5)$，边权为 $1$，因此 $E_4=1+E_5=1$。

节点 $3$ 的状态为 1，且只有一条出边 $(3,5)$，边权为 $1$，因此 $E_3=1+E_5=1$。

节点 $2$ 的状态为 0。

它有两条出边：

• $(2,4)$，边权为 $1$；
• $(2,5)$，边权为 $2$。

由于 $S_2=0$，旅行者会等概率选择一条出边，因此 $\displaystyle E_2=\frac{1}{2}(1+E_4)+\frac{1}{2}(2+E_5)$。

代入 $E_4=1,E_5=0$，得到 $\displaystyle E_2=\frac{1}{2}\times2+\frac{1}{2}\times2=2$。

节点 $1$ 的状态为 1。

从节点 $1$ 到终点 $5$ 的路径共有：

1. $1\to2\to4\to5$，总边权为 $1+1+1=3$；
2. $1\to2\to5$，总边权为 $1+2=3$；
3. $1\to3\to5$，总边权为 $2+1=3$。

三条路径的长度均为 $3$，因此它们全部都是从节点 $1$ 到终点 $5$ 的最短路径。

其中：

• 有 $2$ 条最短路径以边 $(1,2)$ 作为第一条边；
• 有 $1$ 条最短路径以边 $(1,3)$ 作为第一条边。

因此，旅行者选择边 $(1,2)$ 和 $(1,3)$ 的概率分别为 $\dfrac{2}{3}$ 和 $\dfrac{1}{3}$。

于是 $\displaystyle E_1=\frac{2}{3}(1+E_2)+\frac{1}{3}(2+E_3)$。

代入 $E_2=2,E_3=1$，得到 $\displaystyle E_1=\frac{2}{3}\times3+\frac{1}{3}\times3=3$。

因此各节点的期望总距离依次为 $3,2,1,1,0$。