407236: GYM102700 F Free restricted flights

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$$$ $$$\leq$$$ $$$n,m$$$ $$$\leq$$$ $$$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$$$ $$$\leq$$$ $$$a,b$$$ $$$<$$$ $$$n$$$, $$$a \neq b$$$, $$$0$$$ $$$\leq$$$ $$$k$$$ $$$\le$$$ $$$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$$$ $$$\leq$$$ $$$u,v$$$ $$$<$$$ $$$n$$$, $$$u \neq v$$$) and $$$w$$$ ($$$1$$$ $$$\leq$$$ $$$w$$$ $$$\leq$$$ $$$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 ">:(".

4 5
0 1 2
0 2 2
1 2 2
2 3 2
3 0 2
3 1 2

2 4

3 3
0 1 0
0 1 1
0 2 1
1 2 1

>:(

3 3
0 1 0
0 1 1
1 2 1
2 0 1

2 6