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

## Sample Input 1

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

## Sample Output 1

8