有 $n$ 个城市，用 $m$ 条单向道路连接。
第 $i$ 条道路的长度是 $a_i$，如果对其进行翻修，则长度变为 $b_i$。
$1$ 号城市是首都，有 $k$ 个省会城市。
你希望首都到省会城市的最短距离的最大值尽可能小，但是你不能翻修太多道路。
对于所有 $x\in[0,m]$ 求出翻修 $x$ 条道路之后最小的最大值。
输入格式
第一行三个正整数 $n,m,k$。
第二行 $k$ 个正整数，第 $i$ 个 为 $p_i$，表示所有省会城市。
接下来 $m$ 行，第 $i$ 行四个正整数 $x_i,y_i,a_i,b_i$ 表示 $x_i$ 到 $y_i$ 有一条单向道路，翻修前后长度为 $a_i,b_i$。
输出格式
一行 $m+1$ 个正整数，分别表示 $x=0,1\cdots m$ 时的答案。
样例输入
3 3 2
2 3
1 2 12 5
1 3 9 8
2 3 5 2样例输出
12 9 7 7
样例解释
不翻修道路，$1$ 到 $2$ 的最短距离为 $12$，$1$ 到 $3$ 为 $9$，答案为 $12$。
翻修第一条道路，$1$ 到 $2$ 的最短距离变为 $5$，答案为 $9$。
翻修第一条和第三条道路，$1$ 到 $3$ 的最短距离变为 $7$，答案为 $7$。
数据范围
保证从 $1$ 号点出发能到达所有点，$k< n$,$p_i\in[2,n]$ 且互不相同，$x_i,y_i\in[1,n]$，$1\leq b_i\leq a_i \leq 10^5$。
不保证无重边自环。
$n,m\leq 100,k\leq 8$。
Subtask 1（15pts）：$n,m\leq 10$。
Subtask 2（15pts）：$k=1$。
Subtask 3（15pts）：$k=2$。
Subtask 4（55pts）：无特殊限制。
时间限制：1s。
空间限制：256MB。