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