To celebrate being able to reconstruct his array, Max has decided to solve Single Source Shortest Path but wants it to be harder, so he came up with the following problem:

Given a graph of vertices with bidirectional-weighted edges and toggles for the bits for any given edge weight you travel, find the shortest path from to .

The toggle allows you to set the bit to at most once on any edge weight you travel on from to .

You can use multiple toggles on the same edge.

What is the minimum cost to travel from to using at most of the toggles?

#### Constraints

The data are generated such that there is always a path of edges from to .

**Note the increased constraints on .**

#### Input Specification

The first line will contain three integers, , , and , the number of vertices, edges, and toggles, respectively.

The next lines will contain an integer, , the toggle that can be used to set the bit of any edge weight that is travelled on from to to .

The next lines will contain three integers, , , and , a bidirectional edge from to with a weight of .

#### Output Specification

Output the minimum distance from to after using at most of the toggles.

#### Sample Input

```
3 3 3
1
2
3
1 3 1
1 2 2
2 3 12
```

#### Sample Output

`0`

#### Explanation for Sample

It is optimal to take the path to get a distance of : use on the edge from to , giving a weight of ; use on the edge from to , giving a weight of ; use on the edge from to again, giving a weight of .

## Comments