Problem Description

Given a directed weighted network \( G = (V, E) \) with a weight function \( w: E \rightarrow \mathbb{Z}^{*} \) (i.e., the weight \( w(e) \) of any edge \( e \) is a positive integer), and vertices \( s, t \in E \), such that there is no path from \( s \) to \( t \) in \( G' = (V, E - S) \).

Let \( \mathfrak{S} \) be the set of all edge sets \( S \) that satisfy the condition, output the sum of edge weights of the first \( k \) smallest edge sets in \( \mathfrak{S} \) sorted by \( w(S) \) in ascending order. Here, \( w(S) = \sum_{e \in S} w(e) \).

Input Format

The first line contains 5 positive integers \( n, m, s, t, k \), where \( s, t, k \) are as described above, and \( n, m \) represent the number of vertices and edges respectively. The nodes in the graph are numbered from 1 to \( n \). It is guaranteed that \( s \neq t \).

The next \( m \) lines each contain 3 integers \( x, y, z \), representing an edge from \( x \) to \( y \) with weight \( z \). There may be multiple edges but no self-loops.

Output Format

If \( \lvert \mathfrak{S} \rvert < k \), output \( \lvert \mathfrak{S} \rvert \) lines, each containing an integer representing the first \( \lvert \mathfrak{S} \rvert \) values of \( w(S) \); then output one line containing the integer \(-1\).

If \( \lvert \mathfrak{S} \rvert \geq k \), output \( k \) lines, each representing the first \( k \) values of \( w(S) \).

In both cases, the output should be sorted by \( w(S) \) in ascending order.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8
9
12
-1

Sample Input #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

Sample Output #2

116468
117192
118265
120223
145438
147235
149193
157556
158280
161311

Notes/Hints

见题面 Input 部分

见题面 Output 部分