题目描述
给出一个有向带权网络 G=(V,E)，权值函数 w:E→Z∗（即任意边 e 的权值 w(e) 均为正整数），和点 s,t∈E，使得在 G′=(V，E−S) 上不存在 s 到 t 的路 径。
设 Ϭ 是所有满足条件的边集 S 的全集，按 w(S) 从小到大输出 Ϭ 中前 k 小的边集的边权和。其中 $w(S)=∑_{e\in S} w (e)$。
输入格式
第一行包含 5 个正整数 n,m,s,t,k，其中 s,t,k 意义如上，n,m 分别表示 ∣V∣,∣E∣（即点数和边数）。规定图中的节点用 1 到 n 的整数表示。保证 s≠t。
接下来 m 行，每行 3 个整数 x,y,z，表示一条边权为 z 的从 x 到 y 的边。可能有重边但保证没有自环。
输出格式
给出一个有向带权网络 G=(V,E)，权值函数 w:E→Z∗（即任意边 e 的权值 w(e) 均为正整数），和点 s,t∈E，使得在 G′=(V，E−S) 上不存在 s 到 t 的路 径。
设 Ϭ 是所有满足条件的边集 S 的全集，按 w(S) 从小到大输出 Ϭ 中前 k 小的边集的边权和。
样例 1
input
3 3 1 3 100
1 2 3
2 3 4
1 3 5output
8
9
12
-1样例 2
input
5 8 1 5 10
1 2 45176
1 3 41088
1 4 32001
2 5 48931
3 5 39291
4 5 28970
2 3 48131
4 2 49795output
116468
117192
118265
120223
145438
147235
149193
157556
158280
161311没有大样例。
说明与提示
对于测试点 1-2：$n\leq 10,m\leq 20,k\leq 10^6, w\leq 65536$
对于测试点 3-6：$n\leq 50,m\leq 100,k\leq 100, w\leq 65536$
对于数据点 7-10：$n=3000,m=2n-4,k\leq 5\times 10^5$，保证 $s$ 节点向所有非源汇节点有出边，所有非源汇节点向 $t$ 节点有出边，边权不超过 $2^{31}-1$。
对于数据点 11-14：$n=1.5\times 10^5,m=2n-4,k\leq 5\times 10^5$，保证 $s$ 节点向所有非源汇节点有出边，所有非源汇节点向 $t$ 节点有出边，边权不超过 $2^{31}-1$
对于数据点 15-20：$n\leq50,m\leq 1500,k\leq 100$。