Discount

0

0 votes
Problem

There are N cities  in you country, you are currently in city 1 and want to  reach destination city N. For each road you will be given three parameters L,R and W indicating there is an road from city L to city R (Only Uni-Directional movement is allowed), there is an toll which charges W$ if travel v.i.a  this road.

But the cost of travelling is cubersome and suddenly you realise your uncle is M.L.A (Vidhayak). Using that to your advantage you can reduce cost of any K roads and set their toll charge to half of original price (Rounded Down). 

You can assume there is atleast one path from city 1 to city N.

Find the minimum cost to travel from city 1 to city N.

Input:

  • First Line contains three space seperated integers N,M and K.
  • Next M lines contains three integers L,R and W.

Output:

  • Print an single integer as described in the problem.

Constraints:

  • 1N100000
  • 1M200000
  • 1K10
  • 1L,RN
  • 1W109
Time Limit: 3.5
Memory Limit: 256
Source Limit:
Explanation

There are two paths from 1 to 4. In one path there is exactly one edge of weight 4, which can be compressed to 2 using M.L.A power.

Note that in another path minimum cost will be 2+4/2 =4.

Editor Image

?