题目描述

给出一个有向带权网络 \(G = (V, E)\)，权值函数 \(w: E \rightarrow \mathbb{Z^{*}}\)（即任意边 \(e\) 的权值 \(w(e)\) 均为正整数），和点 \(s, t \in E\)，使得在 \(G' = (V, E - S)\) 上不存在 \(s\) 到 \(t\) 的路径。

设 \(\mathfrak{S}\) 是所有满足条件的边集 \(S\) 的全集，按 \(w(S)\) 从小到大输出 \(\mathfrak{S}\) 中前 \(k\) 小的边集的边权和。其中 \(w(S) = \sum_{e \in S} w(e)\)。

输入

第一行，包含5个整数 \(n,m,s,t,k\)，其中 \(s,t,k\) 意义如上，\(n,m\) 分别表示 \(\lvert V \rvert\),\(\lvert E \rvert\)（即点数和边数）。规定图中的节点用 \(1\) 到 \(n\) 的整数表示。保证 \(s \neq t\)。

接下来 \(m\) 行，每行包含 \(3\) 个整数 \(x,y,z\)，表示一条边权为 \(z\) 的从 \(x\) 到 \(y\) 的边。可能有重边但保证没有自环。

输出

如果 \(\lvert \mathfrak{S} \rvert < k\)，先输出 \(\lvert \mathfrak{S} \rvert\) 行，每行包含一个整数，表示前 \(\lvert \mathfrak{S} \rvert\) 个 \(w(S)\)；再输出一行一个整数 \(-1\)。

如果 \(\lvert \mathfrak{S} \rvert \geq k\)，则输出 \(k\) 行，表示前 \(k\) 个 \(w(S)\)。

两种情况均需按照 \(w(S)\) 从小到大输出。

样例 1

输入

3 3 1 3 100
1 2 3
2 3 4
1 3 5

输出

8
9
12
-1

样例 2

输入

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 49795

输出

116468
117192
118265
120223
145438
147235
149193
157556
158280
161311

数据范围限制

测试点编号	\(n \le\)	\(m\)	\(k \le\)	约束
\(1 \sim 2\)	\(10\)	\(\le 20\)	\({10}^6\)	边权不超过 \(65536\)
\(3 \sim 6\)	\(50\)	\(\le 100\)	\(100\)	边权不超过 \(65536\)
\(7 \sim 10\)	\(3000\)	\(= 2 n - 4\)	\(5 \times {10}^5\)	\(s\) 有边连向所有非 \(t\) 节点，所有非 \(s\) 结点有边连向 \(t\)，边权不超过 \(2^{31} - 1\)
\(11 \sim 14\)	\(1.5 \times {10}^5\)	\(= 2 n - 4\)	\(5 \times {10}^5\)	\(s\) 有边连向所有非 \(t\) 节点，所有非 \(s\) 结点有边连向 \(t\)，边权不超过 \(2^{31} - 1\)
\(15 \sim 20\)	\(50\)	\(\le 1500\)	\(100\)	边权不超过 \(65536\)

限制

每个测试点时限：2秒
内存限制：256MB

来源

WC2015