Earliest Arrival Time

A well‐known network company has finally gained some reputation and started receiving orders. Their largest order came from city B. Blue Mary, determined to secure this order, decides to travel there personally. To cut down on travel costs, his financial advisor advises him to purchase tickets only from U Airlines. U Airlines operates exactly one flight per day, departing in the morning and arriving in the afternoon – meaning that each person can only take one flight per day.

The company has obtained detailed information about every flight operated by U Airlines. For each flight, the following information is provided:

• The departure city
• The arrival city
• The maximum number of tickets that can be purchased on any given day for that flight. Note that for a fixed flight, this number is the same for every day (denoted by \(c\)).

Although Blue Mary has already confirmed that it is possible to travel from city A to city B using only U Airlines flights, the ticket‐number restrictions may prevent all travelers from arriving in city B on the same day. Therefore, Blue Mary needs your help to plan the travel schedule so that the arrival time of the last person (i.e. the makespan) is as early as possible.

The problem can be modeled as a minimum arrival time problem with capacity restrictions on daily flights. Formally, given:

• An integer \(P\) denoting the total number of people who must start at city A.
• An integer \(N\) denoting the number of cities (cities are numbered from 1 to \(N\), with city A = 1 and city B = \(N\)).
• An integer \(M\) denoting the number of flights.
• For each flight, three integers: \(u, v, c\) representing a flight from city \(u\) to city \(v\) with a ticket capacity of \(c\) per day.

Each flight operates once per day. A person may only take one flight per day; however, if a person reaches city B earlier than the final arrival day, they can choose to wait (by taking a waiting edge with unlimited capacity) until the designated last day. Using a time–expansion technique, you can build a network where the nodes represent a city on a specific day and the edges represent either taking a flight (with capacity \(c\)) or waiting (with infinite capacity). If we index days from 0 to \(D\) (with the journey starting at day 0 at city A), then a flight taken on day \(d+1\) is modeled as an edge from the node (city, \(d\)) to (destination city, \(d+1\)).

Your task is to compute the smallest day \(D\) such that it is possible to route all \(P\) people from city A to city B by day \(D\).

The main challenge is to account for the daily flight capacity restrictions and the fact that each person can only take one flight per day. Use techniques such as binary search on the number of days and maximum flow algorithms (e.g. Dinic’s algorithm) on the time–expanded network to solve the problem.

Input (in one test case):

P N M
u1 v1 c1
u2 v2 c2
... 
uM vM cM

Output:

D

Constraints:

• 1 ≤ P ≤ 10⁵
• 2 ≤ N ≤ 10³
• 1 ≤ M ≤ 10⁴
• 1 ≤ u, v ≤ N, u ≠ v
• 1 ≤ c ≤ 10⁵

Note: It is guaranteed that a path from city A to city B exists using U Airlines flights.

inputFormat

The first line of the input contains three integers: P, N and M, where P is the total number of people, N is the number of cities (with cities numbered from 1 to N, where city 1 is A and city N is B), and M is the number of flights.

Each of the following M lines contains three integers u, v and c, representing a flight from city u to city v with a ticket capacity of c per day.

outputFormat

Output a single integer D, representing the earliest day by which all people can arrive at city B.

sample

3 4 4
1 2 2
2 4 1
1 3 1
3 4 2

3