问题描述

勇士小蓝准备去遥远的 LQ 迷宫探险，拿到迷宫中的宝藏。迷宫可以看做是一个具有 $N$ 个顶点(顶点编号为 $0∼N-1$) 和 $M$ 条边的无向图，其中每个顶点上都有一只怪物，每只怪物都具有一定的攻击力，每条边都具有一个权重 $w$ 表示小蓝经过边时消耗的时间。

想要拿到迷宫宝藏，小蓝需要从 $0$ 号顶点出发对地图进行探险，在经过顶点时可以对怪物进行击杀，小蓝具有必杀技，能保证一招就击败怪物，但在小蓝对某个怪物进行击杀时，与这个怪物所在结点相邻接的结点上仍存活着的怪物会对小蓝发起一次攻击(注意，不包括小蓝正在击杀的怪物)，小蓝会减少对应攻击力大小的血量。当小蓝击杀完所有怪物并且到达顶点 $N-1$，并且此时小蓝的血量大于 $0$，那么小蓝才可以获得迷宫宝藏。

注意，小蓝的必杀技很快，因此在击杀怪物时可以视为不消耗时间;一个怪物只需要被击杀一次就会消失，只有在小蓝击杀怪物时，与其相邻接的结点上的怪物才会对小蓝发起一次攻击。

如果小蓝可以获得迷宫宝藏，请你输出所需要的最小时间。否则输出 -1 即可。

输入格式

输入的第一行包含三个整数 $N,M,HP$，相邻的整数之间使用一个空格分隔，分别表示顶点数、无向边数以及小蓝初始时侯的血量。

第二行包含 $N$ 个整数，相邻的整数之间使用一个空格分隔，其中第 $i(0≤i≤N−1)$ 个整数表示编号为 $i$ 的顶点上的怪物的攻击力大小;

接下来 $M$ 行，每行包含三个整数 $u,v,w$ 表示在顶点 $u$ 和 $v$ 之间存在一条权重为 $w$ 的无向边。

输出格式

输出一行包含一个整数表示答案，若小蓝无论如何也无法获得迷宫宝藏，则输出 -1。

样例

3 2 10
2 10 5
0 1 1
1 2 2

5

样例说明

小蓝初始在 $0$ 号点，下一步移动到 $1$ 号点，耗费时间 $1$。

击杀 $1$ 号点的怪物，将会受到 $0$、$2$ 号怪物的攻击，血量减少 $7$，剩余血量为 $3$。

移动到 $0$ 号点，耗费时间 $1$，接着击杀 $0$ 号怪物，不会受到攻击。

移动到 $1$ 号点，再继续移动到 $2$ 号点，耗费时间 $3$，此时击杀 $2$ 号怪物，不会受到攻击，击杀完毕后小蓝剩余 $3$ 血量，满足题目要求，总计耗费时间为 $5$。

评测用例规模与约定

对于 $40\%$ 的评测用例，$1≤N≤10$;

对于所有评测用例，$1≤N≤15$，$1≤M≤N^2$，$1≤HP≤100$，$1≤ 怪物攻击力 ≤10$，$1≤w≤10$。