M. Microwave
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The company Charliebot trades several high-frequency investment strategies on the SBC (Sociedade de Bolsas Computadorizadas). The company cares a great deal about network latency, since the lower it is, the higher the expected return of the strategies.

The fiber optic network currently in use has been mapped into $$$N$$$ points of presence and $$$M$$$ bidirectional links. Charliebot's buy and sell signals originate at its data center (point 1) and need to reach the SBC's co-location facility (point $$$N$$$). For each pair $$$(i,j)$$$ of directly connected points of presence, the latency $$$f_{ij}$$$ in microseconds has been measured.

The network provider has recently installed a bidirectional microwave network between some points of presence and measured its latency as $$$w_{ij}$$$ microseconds. This introduced a new option to reduce latency. However, this network is more expensive, and Charliebot's budget allows hiring at most $$$K$$$ microwave links.

Since a microwave link may need to go around the terrain where it was installed, there is no guarantee that $$$w_{ij} \lt f_{ij}$$$. Furthermore, the network provider guarantees that it will always be possible to find a path in the network even when the budget for microwave links is 0.

What is the smallest possible end-to-end latency, in microseconds?

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 10^{5}$$$, $$$1 \leq M \leq 2 \times 10^{5}$$$, $$$0 \leq K \leq 10$$$).

Each of the following $$$M$$$ lines contains four integers $$$i$$$, $$$j$$$, $$$f_{ij}$$$, and $$$w_{ij}$$$ ($$$1 \leq i, j \leq N$$$, $$$i \neq j$$$, $$$1 \leq f_{ij} \leq 10^{9}$$$, $$$w_{ij} = -1$$$ or $$$1 \leq w_{ij} \leq 10^{9}$$$), describing a direct connection between points of presence $$$i$$$ and $$$j$$$ with latency $$$f_{ij}$$$ on the fiber link and $$$w_{ij}$$$ on the microwave channel. If $$$w_{ij} = -1$$$, there is no microwave channel on that connection. Each pair of points appears in at most one line.

Output

Print a single line containing an integer corresponding to the minimum latency, in microseconds, between Charliebot's data center and the SBC, using at most $$$K$$$ microwave links.

Examples
Input
4 5 1
1 2 10 3
2 4 10 4
1 3 5 -1
3 4 7 2
1 4 30 8
Output
7
Input
3 3 0
1 2 5 2
2 3 7 1
1 3 20 3
Output
12
Note

Explanation for example 1

Since at most one microwave link is allowed, the best route is to go from point 1 to point 3 via the fiber optic link, with a latency of 5 microseconds, and from point 3 to point 4 via the microwave link, with a latency of 2 microseconds. Thus, the total latency is 7 microseconds.