## 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 ≤ 1000000 (30%)
Subtask 2: 1 ≤ S ≤ 1000000, N will fit into a 32-bit signed integer. (70%)
Subtask 3: As per sample testcases

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

```8
```