该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

有 $n$ 个人通过手机消息互相联系，他们之间的联系是单向的：
有的人可以发消息给别人，但别人不一定能回。

给出一份列表 $messages$，其中每一项是
$messages[i] = (a, b, t)$，表示第 $a$ 个人给第 $b$ 个人发消息需要 $t$ 个时间单位。

某天，第 $S$ 个人最先发出一条消息，这条消息会通过这些联系慢慢传给别人。
请计算：要多久，所有人都能收到这条消息？
如果有的人永远收不到消息，就输出 -1。

输入输出格式

第一行为3个整数,n,m,S,分别表示有n个节点、m个边、从第S个人开始发信息

从第二行开始为messages[i]

数据范围

$1<=k <=n <=100\\ 1 <= messages.length <= 6000\\ messages[i].length == 3\\ 1 <= a_i, b_i <=n\\a_i != b_i\\0 <= t_i <=100$

测试样例

输入：

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

输出：

2