The train will inevitably head to the next station, but where will the stage go? And where will you go?

At this moment, you play the role of the "audience," and the lives of $n$ stage girls are intertwined by the "destinies" you choose.

For convenience, we describe a "destiny" connecting stage girls with IDs $u$ and $v$ with a bond value $w$ as a triple $(u, v, w)$.

However, the "destinies" of the stage girls are not entirely under your control. The stage girl with ID $s$, Karen-chan, dominates the "destinies" related to her. Specifically, if a "destiny" $(u, v, w)$ satisfies $u=s \lor v=s$, this "destiny" is dominated by Karen-chan. You have no right to interfere with the "destinies" dominated by Karen-chan. The remaining "destinies" are yours to control freely.

You will choose $a$ "destinies" from those you control (where $a$ is a non-negative integer of your choosing), and Karen-chan must choose exactly $k$ "destinies" related to her. Then, the performance begins.

We say the lives of two stage girls have an intersection if and only if they are connected directly or indirectly by "destinies."

Karen-chan does not like meaningless "destinies," so she requires that she cannot be directly connected to the same person by multiple "destinies." Karen-chan also does not wish to see everyone drift apart, so she requires that the lives of all $n$ stage girls must have intersections; otherwise, she will go on strike.

Let $A$ be the set of bond values of the $a+k$ "destinies" finally chosen. We define the "turbulence value" of $A$ as:

$$\sum_{i=1}^{a+k}{\rm max_i}(A)\times (10^9+7)^{-i}$$

where ${\rm max}_i(A)$ denotes the $i$-th largest value in the set $A$.

The "audience" and the stage girls are inseparable. Now you need to cooperate with Karen-chan to present a performance with the minimum turbulence value. For convenience, you only need to output the sum of the bond values of the "destinies" you finally choose. If no performance satisfies Karen-chan's requirements, output nonnondayo.

Formal Problem Statement

Given $m$ edges, you need to select a set of edges such that the graph is connected and the degree of the vertex with ID $s$ is exactly $k$. Furthermore, you cannot select multiple edges between $s$ and the same vertex. Find a scheme that minimizes the above expression and output the sum of the weights of the selected edges. If no solution exists, output nonnondayo.

Input

The first line contains four integers $n, m, k, s$.

The next $m$ lines each contain three integers $u, v, w$, representing a "destiny."

Output

Output a single integer representing the sum of the bond values of the "destinies" you finally choose. If no solution exists, output nonnondayo.

Examples

Input 1

4 4 2 1
1 2 1
1 3 2
3 4 3
1 4 4

Output 1

6

Constraints

For all data, $1 \leq k < n \leq 5 \times 10^4$, $m \leq 5 \times 10^5$, $w \leq 10^9$. There are multiple edges but no self-loops, and all $w_i$ are distinct.

• Subtask 1 (5 points): $m = n - 1$.
• Subtask 2 (10 points): $n, m \leq 21$.
• Subtask 3 (15 points): $n \leq 1000$, $m \leq 3 \times 10^3$.
• Subtask 4 (20 points): It is guaranteed that after removing the vertex with ID $s$ and all edges related to $s$, the remaining graph is a forest.
• Subtask 5 (10 points): Exactly $k$ edges $(u_i, v_i)$ satisfy the condition that one of the endpoints is $s$.
• Subtask 6 (20 points): $n \leq 10^4$, $m \leq 10^5$.
• Subtask 7 (20 points): $n \leq 5 \times 10^4$, $m \leq 5 \times 10^5$.