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 .

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No additional constraints.

#### 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

Can someone take a look at my submission? I am fairly certain that I have the correct overall solution, but must have made a mistake in implementing it. link: https://dmoj.ca/submission/5177712

You are using a toggle for the same bit on the same edge multiple times (a bit can be toggled at most once for one edge).

Consider this test case:

If you want further help debugging, I recommend joining the DMOJ Discord and using the help forum.

got it, thanks.