#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Samuel lives in a one-dimensional world. RI is at the leftmost point in this one-dimensional world. After programming training, Samuel is heading home from school. His house is located *N* kilometers away. In this one-dimensional world, there are bus stops that are spaced 1 kilometer apart. *S* shuttle buses run from one bus stop to another, but only travel in the right direction.

Each shuttle bus costs a certain amount of money to ride. Alternatively, Samuel can also take a taxi between certain bus stops, which charge a flat rate of *R* dollars per kilometer. Given the list of shuttle buses and their respective sources, destinations and cost, output the least amount of money in dollars Samuel can use to reach home.

## Input

The first line of input will contain three integers, *N*, *S* and *R*.

The next *S* lines of input will contain three integers each, the source, the destination and the cost of the shuttle *i*.

## Output

Your output should contain one integer, the least amount of money in dollars Samuel can use to reach home.

## Limits

Subtask 1: 1 ≤ N, S ≤ 10 (20%)

Subtask 2: 1 ≤ N, S ≤ 1000 (30%)

Subtask 3: 1 ≤ N, S ≤ 1000000 (50%)

Subtask 4: As per sample testcases

## Sample Input 1

5 3 3 0 4 6 3 5 3 4 5 2

## Sample Output 1

8

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 10 | 3s | 128MB | Minimum |

2 | 30 | 10 | 3s | 128MB | Minimum |

3 | 50 | 10 | 3s | 128MB | Minimum |

4 | 0 | 1 | 3s | 128MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o goinghome -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512