两只 Bugcat 计划进行一次聚会。它们居住的地图由 $n$ 个节点和 $m$ 条有向边组成。第一只 Bugcat 从节点 $1$ 出发，第二只 Bugcat 从节点 $n$ 出发。

每条边 $i$ 连接节点 $x_i$ 到节点 $y_i$。有两种方式可以通过一条边：

• 步行：消耗 $z_i$ 单位的耐力值。
• 搭乘出租车：花费 $1$ 元，但消耗 $0$ 单位的耐力值。

两只 Bugcat 的总预算共计 $w$ 元。只要不超过总预算，它们可以随时选择在任意边上搭乘出租车。

你的任务是求在预算限制下，两只 Bugcat 为了在同一个节点相遇所必须消耗的最小耐力消耗之和。如果两只 Bugcat 无法相遇，则输出 $-1$。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据，第一行包含三个整数 $n, m, w$（$\sum n, \sum m \le 1000, 0 \le w \le 1000$），分别表示节点数、边数和总预算。

接下来的 $m$ 行，每行包含三个整数 $x_i, y_i, z_i$（$1 \le x_i, y_i \le n, 1 \le z_i \le 10^9$），表示一条从 $x_i$ 到 $y_i$ 的有向边，其步行的耐力消耗为 $z_i$。

输出格式

对于每组测试数据，输出一行，表示两只 Bugcat 相遇所需的最小耐力消耗之和。如果两只 Bugcat 无法相遇，则输出 $-1$。

样例

输入样例 1

2
5 5 2
1 2 3
1 3 4
5 4 2
4 3 1
2 3 100
5 4 2
1 2 3
1 3 4
5 4 2
2 3 100

输出样例 1

1
-1