11222: 追债之旅
[Creator : ]
Description
小明现在要追讨一笔债务，已知有 $n$ 座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。
小明一开始位于编号为 $1$ 的城市，欠债人位于编号为 $n$ 的城市。
小明每次从一个城市到达另一个城市需要耗时 $1$ 天，而欠债人每天都会挥霍一定的钱，等到第 $k$ 天后（即第 $k+1$ 天）他就会离开城 $n$ 并再也找不到了。
小明必须要在他离开前抓到他（最开始为第 $0$ 天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？
Input
第 $1$ 行输入三个整数 $n,m,k$，代表城市数量，道路数量和指定天数。
第 $2 \sim m+1$ 行，每行输入三个整数 $u,v,w$，代表起点城市，终点城市和支付费用。（数据保证无重边，自环）
第 $m+2$ 行输入 $k$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 天欠债人会挥霍的钱。
Output
输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第 $k$ 天及之前到达城 $n$），则输出 $-1$。
Constraints
数据保证：$0<n≤1000,\ 0<m≤10000,\ 0<k≤10,\ 1≤u,v≤n,\ 0<w,a_i≤1000$
Sample 1 Input
3 3 2
1 3 10
1 2 2
2 3 2
3 7
Sample 1 Output
13
小明从 $1\to 3$，总共费用=10（行程）+3（挥霍费用）=13，是方案中最小的（另一条方案花费14）。
Sample 2 Input
3 2 1
1 2 3
2 3 3
10
Sample 2 Output
-1
小明无法在第1天赶到城3，所以输出-1。