CF576D Flights for Regular Customers

In the country there are exactly $ n $ cities numbered with positive integers from $ 1 $ to $ n $ . In each city there is an airport is located. Also, there is the only one airline, which makes $ m $ flights. Unfortunately, to use them, you need to be a regular customer of this company, namely, you have the opportunity to enjoy flight $ i $ from city $ a_{i} $ to city $ b_{i} $ only if you have already made at least $ d_{i} $ flights before that. Please note that flight $ i $ flies exactly from city $ a_{i} $ to city $ b_{i} $ . It can not be used to fly from city $ b_{i} $ to city $ a_{i} $ . An interesting fact is that there may possibly be recreational flights with a beautiful view of the sky, which begin and end in the same city. You need to get from city $ 1 $ to city $ n $ . Unfortunately, you've never traveled by plane before. What minimum number of flights you have to perform in order to get to city $ n $ ? Note that the same flight can be used multiple times.

N/A

N/A