Network Delay Time

Given directed weighted edges and a starting node, return the time required for all nodes to receive the signal. If some node is unreachable, return -1. Pattern focus: Dijkstra. Use a distance map and always expand the currently smallest tentative distance first.

Input Format

times = directed weighted edges [u, v, w], n = node count, k = starting node

Output Format

time needed for all nodes to receive the signal, or -1

Constraints

• 1 <= n <= 100
• 1 <= times.length <= 6000
• 1 <= ui, vi <= n
• 0 <= wi <= 100

Examples

times = [[2,1,1],[2,3,1],[3,4,1]]
n = 4
k = 2

2

times = [[1,2,1]]
n = 2
k = 1

1

times = [[1,2,1]]
n = 2
k = 2

-1