列车必将驶向下一站，而舞台将前往何处？你们又将前往何处？
在此刻，你扮演着「观众」 ，$ 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 $。