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:
Output:
Constraints:
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.