题目描述

给定一个包含 n 个节点的网络，节点编号从 1 到 n。你还会得到一个 times 列表，表示传输时间为有向边，times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，wi 是从源节点到目标节点传输信号所需的时间。

我们将从一个给定的节点 k 发送信号。返回让所有 n 个节点都接收到信号所需的最短时间。如果有的节点无法接收到信号，返回 $-1$。

输入格式

输入的第一行包含$3$个整数，$n$表示节点的数量，$m$表示有向边数量，$k$表示信号源的编号。

接下来 $m$ 行，每行 $3$ 个整数表示有向边的节点编号，以及边的权重。

输出格式

输出$1$个整数，表示让所有 $n$ 个节点都接收到信号所需的最短时间，如果有的节点无法接收到信号，则输出 $-1$。

样例

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

2

2 1 1
1 2 1

1

2 1 2
1 2 1

-1

约束

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有的对 (ui, vi) 都是唯一的（即没有多重边）。