列车必将驶向下一站,而舞台将前往何处?你们又将前往何处?
在此刻,你扮演着「观众」 ,n 位舞台少女的人生因你所选择的「命运」 而交织在一起。
为了方便理解,我们用一个三元组 (u,v,w) 来描述一条连接编号为 u,v 的舞台少女,羁绊值为 w 的「命运」。
可是,舞台少女的「命运」并不完全被你所掌握。编号为 s 的舞台少女 Karen 酱,支配着与她自己有关的「命运」。具体地,若一条「命运」(u,v,w) 满足 u=s∨v=s ,则这条「命运」被 Karen 酱支配着。被 Karen 酱支配的「命运」你无权干涉。而其余的「命运」则可供你自由支配。
你将从你所支配的「命运」中选择 a 条出来( a 是一个由你选择的非负整数),而 Karen 酱则必须选择恰好 k 条与她有关的「命运」。然后,演出开始。
我们称两位舞台少女的人生是有交集的,当且仅当她们被「命运」直接或间接地连接着。
Karen 酱不喜欢无意义的「命运」,所以她要求自己不能与同一个人直接连接着多条「命运」; Karen 酱也不希望看见大家渐行渐远,所以她要求所有 n 位舞台少 女的人生都相互有交集,否则将会罢演。
设最终选择的 a+k 条「命运」的羁绊值所构成的集合为 A ,定义 A 的颠沛值为:
a+k∑i=1maxi(A)×(109+7)−i
其中 maxi(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≤k<n≤5×104,m≤5×105,w≤109。有重边无自环,wi 互不相同。
- 子任务 1(5 分):m=n−1。
- 子任务 2(10 分):n,m≤21。
- 子任务 3(15 分):n≤1000,m≤3×103。
- 子任务 4(20 分):保证去掉编号为 s 的点和与 s 有关的边后,剩下的图为森林。
- 子任务 5(10 分):满足恰有 k 条边 (ui,vi) 满足其中一个端点为 s​ 。
- 子任务 6(20 分):n≤104,m≤105。
- 子任务 7(20 分):n≤5×104,m≤5×105。