Problem 3772: Tilted Towers

Task

You are given an undirected weighted graph with $N$ nodes and $M$ edges. You are also given two integers: $Q$ and $P$ .

Your task is to determine the minimum cost path from node $1$ to node $N$ , with the following conditions:

The path is not required to be simple, meaning you may traverse the same edge multiple times.
At each step along the path, you have two options:
1. You can traverse a single edge, paying its original cost.
2. You can choose to traverse $2^X$ consecutive edges (for some $0 \le X \le Q$ ), where the cost of each edge is replaced with $P$ instead of its original cost.

Important constraint:

The values of $X$ you choose must be pairwise distinct, meaning that each shortcut $2^X$ can be used at most once in the entire path.
For example, if you use a shortcut of length $2^1$ , you cannot use length $2^1$ again — but you may still use $2^2 = 4$ or $2^3 = 8$ , as long as each $X \le Q$ is unique.

Input data

On the first line, there will be the four numbers $N$ , $M$ , $Q$ , and $P$ with the meaning from the statement, separated by a single space.
On the next $M$ lines, the edges of the graph will be described.
On each such line, there will be $3$ numbers: $A$ , $B$ , $C$ (separated by a single space), meaning that there is an edge between nodes $A$ and $B$ with cost $C$ .

Output data

The first line will contain a single number, representing the minimum cost of a path from node $1$ to node $N$ .

Constraints and clarifications

$1 \le A, B \le N \le 500$
$1 \le M \le \frac{N*(N-1)}{2}$
$1 \le Q \le 9$
$1 \le C, P \le 10^9$
The given graph is connected.

Example 1

stdin

stdout

Example 2