列车必将驶向下一站，而舞台将前往何处？你们又将前往何处？

在此刻，你扮演着「观众」 ，$n$ 位舞台少女的人生因你所选择的「命运」 而交织在一起。

为了方便理解，我们用一个三元组 $(u,v,w)$ 来描述一条连接编号为 $u,v$ 的舞台少女，羁绊值为 $w$ 的「命运」。

可是，舞台少女的「命运」并不完全被你所掌握。编号为 $s$ 的舞台少女 Karen 酱，支配着与她自己有关的「命运」。具体地，若一条「命运」$(u,v,w)$ 满足 $u=s \lor v=s$ ，则这条「命运」被 Karen 酱支配着。被 Karen 酱支配的「命运」你无权干涉。而其余的「命运」则可供你自由支配。

你将从你所支配的「命运」中选择 $a$ 条出来（ $a$ 是一个由你选择的非负整数），而 Karen 酱则必须选择恰好 $k$ 条与她有关的「命运」。然后，演出开始。

我们称两位舞台少女的人生是有交集的，当且仅当她们被「命运」直接或间接地连接着。

Karen 酱不喜欢无意义的「命运」，所以她要求自己不能与同一个人直接连接着多条「命运」； Karen 酱也不希望看见大家渐行渐远，所以她要求所有 $n$ 位舞台少 女的人生都相互有交集，否则将会罢演。

设最终选择的 $a+k$ 条「命运」的羁绊值所构成的集合为 $A$ ，定义 $A$ 的颠沛值为：

$$\sum_{i=1}^{a+k}{\rm max_i}(A)\times (10^9+7)^{-i} $$

其中 ${\rm max}_i(A)$ 表示集合 $A$ 中第 $i$ 大的数。 「观众」和舞台少女密不可分，现在你需要和 Karen 酱合作，一同献上颠沛值最小的演出。为了方便，你只需要输出你们最终选择的「命运」的羁绊值之和。 若不存在满足 Karen 酱要求的演出，则输出 nonnondayo。

形式化题意

给定 $m$ 条边，你需要选出若干条边满足图联通并且编号为 $s$ 的点度数恰为 $k$。并且与 $s$ 有关的边不能选择重边。找到一种上述式子最小的方案并输出选择的边权和。 无解输出 nonnondayo。

输入格式

第一行四个整数 $n,m,k,s$。

接下来 $m$ 行，每行三个整数 $u,v,w$ 表示一条「命运」。

输出格式

一行一个整数表示你们最终选择的「命运」的羁绊值之和，不存在方案则输出 nonnondayo。

样例 1

input

4 4 2 1
1 2 1
1 3 2
3 4 3
1 4 4

output

6

数据范围

对于所有数据满足 $1\leq k<n\leq 5\times 10^4$，$m\leq 5\times 10^5,w\leq 10^9$。有重边无自环，$w_i$ 互不相同。

• 子任务 1（5 分）：$m=n-1$。
• 子任务 2（10 分）：$n,m\leq 21$。
• 子任务 3（15 分）：$n\leq 1000$，$m\leq 3\times 10^3$。
• 子任务 4（20 分）：保证去掉编号为 $s$ 的点和与 $s$ 有关的边后，剩下的图为森林。
• 子任务 5（10 分）：满足恰有 $k$ 条边 $(u_i,v_i)$ 满足其中一个端点为 $s$​ 。
• 子任务 6（20 分）：$n\leq 10^4$，$m\leq 10^5$。
• 子任务 7（20 分）：$n\leq 5\times 10^4$，$m\leq 5\times 10^5$。