说明

有 $n$ 个网络节点，标记为 $1$ 到 $n$。 节点间有 $m$ 条有向边，每条边分别记为 $u,v,w$，分别表示源节点、目标节点以及从源节点到目标节点需要的传输时间。

如果一个信号从节点 $a$ 通过节点 $b$ 中转传输到节点 $c$，所需的时间为从 $a$ 到 $b$ 的时间加上 $b$ 到 $c$ 的时间，不考虑中转产生的时间损耗。

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

格式

输入

第一行三个整数 $n, m, k$，分别为节点个数、边数以及信号源节点编号； 接下来 $m$ 行，每行三个整数 $u,v,w$，即从 $u$ 到 $v$ 需要花费 $w$ 时间。

输出

一个整数，即使所有节点都收到信号需要的时间，或者有节点无法收到时输出 -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 \leq k \leq n \leq 100$
• $1 \leq m \leq 6000$
• $1 \leq u_i, v_i \leq n$
• $u_i != v_i$
• $0 \leq w_i \leq 100$
• 所有 $(u_i, v_i)$ 对都 互不相同（即，不含重复边）