Alice and Bob are in the middle of a damn pandemic. They wanted to travel together somewhere for summer. However, they are in different countries and since the pandemic started, multiple flights have been canceled. What is worst, their respective countries do not allow tourists to enter, so they have to find another country to see each other. Nevertheless, they are allowed to use any country (including their residence countries) for stopovers.
Alice and Bob have spent nearly all of their money on face masks, toilet paper, and disinfectant. Therefore, they need to minimize the total amount of money spent on flights, including the returning trip to their respective homes. Ironically, Alice and Bob are official members of the United Nihilistic Airlines League (UNAL), which has granted a special $k$-ticket to each of them. A $k$-ticket allows a passenger to take up to $k$ free flights, those tickets are personal and non-transferable.
Can you help them to find the country where they can see each other with minimal cost?
The first line consists of 2 integers separated by a space, $n$ and $m$ ($3$ $<=$ $n, m$ $<=$ $10^4$) — The number of countries, and the number of available flights, respectively.
The next line consists of 3 integers separated by a space, $a$, $b$ and $k$ ($0$ $<=$ $a, b$ $<$ $n$, $a eq.not b$, $0$ $<=$ $k$ $<=$ $10$) — The country where Alice lives, the country where Bob lives, and the amount of free flights available on each $k$-ticket, respectively.
The next $m$ lines contains 3 integers each: $u$, $v$ ($0$ $<=$ $u, v$ $<$ $n$, $u eq.not v$) and $w$ ($1$ $<=$ $w$ $<=$ $10^3$) separated by a space, which represent a flight coming from $u$ into $v$ with cost $w$.
Print two integers separated by a space, the index of the country where Alice and Bob should travel and the total round trip cost for both Alice and Bob. if there are many possible countries with minimal cost print the one with the lowest index.
If Alice and Bob cannot see each other print ">:(".
## Input
The first line consists of 2 integers separated by a space, $n$ and $m$ ($3$ $<=$ $n, m$ $<=$ $10^4$) — The number of countries, and the number of available flights, respectively.The next line consists of 3 integers separated by a space, $a$, $b$ and $k$ ($0$ $<=$ $a, b$ $<$ $n$, $a eq.not b$, $0$ $<=$ $k$ $<=$ $10$) — The country where Alice lives, the country where Bob lives, and the amount of free flights available on each $k$-ticket, respectively.The next $m$ lines contains 3 integers each: $u$, $v$ ($0$ $<=$ $u, v$ $<$ $n$, $u eq.not v$) and $w$ ($1$ $<=$ $w$ $<=$ $10^3$) separated by a space, which represent a flight coming from $u$ into $v$ with cost $w$.
## Output
Print two integers separated by a space, the index of the country where Alice and Bob should travel and the total round trip cost for both Alice and Bob. if there are many possible countries with minimal cost print the one with the lowest index.If Alice and Bob cannot see each other print ">:(".
[samples]
**Definitions**
Let $ G = (V, E) $ be a directed weighted graph, where:
- $ V = \{0, 1, \dots, n-1\} $ is the set of countries.
- $ E \subseteq V \times V \times \mathbb{R}^+ $ is the set of flights, with each edge $ (u, v, w) $ representing a directed flight from $ u $ to $ v $ with cost $ w $.
Let $ a, b \in V $ be Alice’s and Bob’s home countries, respectively, with $ a \ne b $.
Let $ k \in \mathbb{Z}_{\ge 0} $ be the number of free flights per $ k $-ticket (each person gets one ticket).
**Constraints**
1. $ 3 \le n, m \le 10^4 $
2. $ 0 \le a, b < n $, $ a \ne b $
3. $ 0 \le k \le 10 $
4. For each flight $ (u, v, w) \in E $: $ 0 \le u, v < n $, $ u \ne v $, $ 1 \le w \le 10^3 $
**Objective**
Find a destination country $ d \in V $ minimizing the total round-trip cost for both Alice and Bob, accounting for their $ k $-tickets:
- Each person may use up to $ k $ free flights (i.e., the cost of up to $ k $ flights in their entire itinerary is waived).
- The itinerary for each person is: home $ \to $ destination $ \to $ home (a round trip).
- Total cost = sum of paid flight costs (after applying up to $ k $ free flights per person).
Let $ P_A $ be the set of all possible round-trip paths for Alice: $ a \to d \to a $.
Let $ P_B $ be the set of all possible round-trip paths for Bob: $ b \to d \to b $.
For a given $ d $, define:
- $ C_A(d) $: minimum total cost of Alice’s round trip $ a \to d \to a $, using at most $ k $ free flights (i.e., subtract the cost of up to $ k $ most expensive flights in the path).
- $ C_B(d) $: similarly for Bob.
Then total cost for destination $ d $ is:
$$
T(d) = C_A(d) + C_B(d)
$$
Minimize $ T(d) $ over all $ d \in V $. If multiple $ d $ yield minimal $ T(d) $, choose the smallest index.
If no such $ d $ exists (i.e., no path from $ a $ to $ d $ to $ a $, or from $ b $ to $ d $ to $ b $), output “>:(".
**Note**: Since the graph is directed, compute shortest paths in both directions (forward and reverse) for all nodes to determine all possible round-trip costs.