Network Delay Time

Problem Statement

Consider a network composed of M nodes, numbered from 1 to M.

You are given a list delays representing travel times as directed connections. Each element in delays is a tuple (a, b, t), where a is the starting node, b is the destination node, and t is the time it takes for a signal to move from node a to node b.

Starting from node S, a signal is sent out. Determine the minimum time required for the signal to reach all nodes in the network. If not all nodes can receive the signal, return -1.

Examples

Example 1:
delays = [[3,2,2], [3,4,1], [2,1,3]]
M = 4
S = 3
Output: 4

Example 2:
delays = [[1,2,5], [2,3,10], [1,3,15]]
M = 3
S = 1
Output: 15

Example 3:
delays = [[1,2,1]]
M = 2
S = 2
Output: -1
    

Constraints

• M is between 1 and 120 inclusive.
• S is between 1 and M inclusive.
• The length of delays is between 1 and 7000 inclusive.
• Each delay tuple (a, b, t) satisfies: 1 ≤ a, b ≤ M and 0 ≤ t ≤ 120.