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

题目背景

小 T 十分害怕老师。

题目描述

现在有 $n$ 个教室，编号为 $1\sim n$，教室之间有 $m$ 条边，每条边连接 $x_i,y_i$ 号教室，上面有 $v_i$ 个老师。

小 T 一开始处于1号教室，他想要去到 $n$ 号教室，并且碰到尽量少的老师。

为此，他斥巨资购买了 $k$ 个老师消失器，每个老师消失器可以让一条长度不超过 $a_i$ 的简单路径上的老师全部消失。

如果小 T 聪明绝顶，请问他最少碰到几个老师？

题目保证不存在重边，自环。

输入格式

第一行三个整数 $n,m,k$，表示教室数量，路径数量与老师消失器数量。

接下来 $m$ 行，每行三个整数 $x_i,y_i,v_i$，意思见题目描述。

接下来一行 $k$ 个整数 $a_i$，意思见题目描述。

输出格式

输出一个整数，表示小 T 碰到的老师的最小数量。

样例 1

输入

13 14 1
1 2 1
3 4 1
5 6 1
7 13 1
1 9 4
11 12 1
10 11 100
8 9 100
8 13 100
13 12 1
10 9 1
2 3 1
4 5 1
6 7 1
2

输出

4

样例 2

见选手目录下的 class/class2.in 与 class/class2.ans。

该样例满足测试点 $1-2$ 的约束条件。

样例 3

见选手目录下的 class/class3.in 与 class/class3.ans。

该样例满足测试点 $5$ 的约束条件。

样例 4

见选手目录下的 class/class4.in 与 class/class4.ans。

该样例满足测试点 $6-10$ 的约束条件。

数据范围

共 10 组测试数据。

对于所有数据，$1 \le n \le 10^4,1 \le m \le \min(3*10^5,\frac{n(n-1)}{2}),1 \le x_i,y_i \le n,0 \le k \le 5,1 \le a_i \le 10,1 \le v_i \le 10^9$