题目描述

有 $n$ 个网络节点，标记为 $1$ 到 $n$。

给你一个大小为 $m$ 的列表 $times$，表示信号经过 有向 边的传递时间。 $times[i] = (u_i, v_i, w_i)$，其中 $u_i$ 是源节点，$v_i$ 是目标节点， $w_i$ 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 $K$ 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 $-1$ 。

输入格式

第一行三个整数 $n$ $m$ $k$；

接下来的 $m$ 行，每行三个整数表示源节点、目标节点和一个信号从源节点传递到目标节点的时间。

输出格式

一行一个整数表示答案。

示例 1：

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

2

示例 2：

2 1 1
1 2 1

1

示例 3：

2 1 2
1 2 1

-1

提示：

• $1 <= k <= n <= 100$
• $1 <= times.length <= 6000$
• $times[i].length == 3$
• $1 <= u_i, v_i <= n$
• $u_i != v_i$
• $0 <= w_i <= 100$
• 所有 $(u_i, v_i)$ 对都 互不相同（即，不含重复边）

SOURCE

743. 网络延迟时间