A delivery company sends out daily newspapers across a city with n neighborhoods, labeled from 1 to n. Some neighborhoods are connected by one-way roads, and each road takes a certain number of minutes to travel.

Each morning, the company begins delivery from a central warehouse located in neighborhood k, using one or more delivery trucks. Once a truck delivers newspapers to a neighborhood, that neighborhood can immediately dispatch new trucks to deliver newspapers to its connected neighbors, like a relay system.

The road network is provided as a list called roads, where roads[i] = [from, to, time]. This means it takes time minutes to travel from neighborhood from to neighborhood to.

Return the minimum time it takes for all neighborhoods to receive the newspaper. If any neighborhood cannot be reached, return -1.

Example 1:

Input: n = 4, k = 1, roads = [[1, 2, 1], [2, 4, 1], [1, 3, 2], [3, 4, 5]]
Output: 2
Explanation: 
minimum time it takes for all neighborhoods to receive the newspaper is the maximum time it takes to reach any neighborhood, because newspapers are delivered in parallel once they’re on their path.
Neighborhood 2 receives the newspaper at time 1.
Neighborhood 3 receives the newspaper at time 2.
Neighborhood 4 receives the newspaper through path 1 → 2 → 4, which takes 1 + 1 = 2 minutes.
The delivery finishes when the last reachable neighborhood receives the newspaper, so the answer is max(0, 1, 2, 2) = 2.

Example 2:

Input: n = 3, k = 1, roads = [[1, 2, 1], [2, 3, 1], [1, 3, 4]]
Output: 2
Explanation: Fastest: 1 → 2 (1), then 2 → 3 (1) = total minimum time is 2

Example 3:

Input: n = 4, k = 1, roads = [[1, 2, 2], [1, 3, 1]]
Output: -1
Explanation: Node 4 is unreachable from node 1

Constraints

1 <= k <= n <= 100

1 <= roads.length <= 6000

roads[i].length == 3

1 <= from_i, to_i <= n

from_i != to_i

0 <= time_i <= 100

All the pairs (from_i, to_i) are unique. (i.e., no multiple edges.)

79. Newspaper Delivery Time (Dijkstra)