编程题：动态规划
上周乔治先生访问了克罗地亚。由于乔治先生是一个非常重要的人，当他在街上时，警察不允许进入那条街，但在乔治先生之前进入街道的车辆可以继续行驶。
乔治先生来访时，卢卡开着他的卡车在城里转悠。但由于一些街道被封锁，他无法及时送货，几乎失去了工作。虽然现在已经很晚了，但他想知道他如何才能更好地计划自己的交付，即乔治先生来访时，交付所需的最短时间是多少。他知道乔治先生走的路线。
这座城市以十字路口和连接它们的双向街道为模型。对于每一条街道，卢卡都知道他需要多少时间才能穿过（乔治先生也需要同样的时间）。
例如，如果乔治先生在第10分钟开始穿过一条街道，需要5分钟才能离开，这条街道将在第10、11、12、13和14分钟被封锁。卢卡可以在9分钟及之前或15分钟及之后进入街道。
如果卢卡在乔治先生到达后的K分钟内开始开车，那么编写一个程序，计算卢卡完成交付所需的最少时间。
### 输入格式:
第一行包含两个整数$$N$$和$$M（2≤N≤1000, 2≤M≤10000）$$，交叉口的数量和街道的数量。交叉口编号为1到$$N$$。
第二行包含四个整数$$A、B、K$$和$$G（1≤A、B≤N、0≤K≤1000, 0≤G≤1000)$$.
以下是顺序：
•卢卡起点的十字路口；
•卢卡必须到达的十字路口；
•乔治先生和卢卡先生之间的出发时间差（卢卡先生在乔治先生出发后正好K分钟从十字路口A出发）；
•乔治先生路线上的十字路口数量。
第三行包含$$G$$整数，这是交叉点的标签，先生
乔治会来参观。每对相邻的整数表示他将穿过的街道。那条街将会存在，乔治先生最多一次穿过每一条街。
下面的每一条M线都包含三个整数$$A、B$$和$$L$$，这意味着在交叉点$$A$$和$$B$$之间有一条街道，需要$$L$$分钟才能穿过。我会在1到1000之间。
### 输出格式:
输出$$Luka$$交付所需的最少时间（分钟）。
### 输入样例1:
in
6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15
### 输出样例1:
out
21
### 输入样例2:
in
8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23
### 输出样例2:
out
40
答案：若无答案欢迎评论
乔治先生来访时，卢卡开着他的卡车在城里转悠。但由于一些街道被封锁，他无法及时送货，几乎失去了工作。虽然现在已经很晚了，但他想知道他如何才能更好地计划自己的交付，即乔治先生来访时，交付所需的最短时间是多少。他知道乔治先生走的路线。
这座城市以十字路口和连接它们的双向街道为模型。对于每一条街道，卢卡都知道他需要多少时间才能穿过（乔治先生也需要同样的时间）。
例如，如果乔治先生在第10分钟开始穿过一条街道，需要5分钟才能离开，这条街道将在第10、11、12、13和14分钟被封锁。卢卡可以在9分钟及之前或15分钟及之后进入街道。
如果卢卡在乔治先生到达后的K分钟内开始开车，那么编写一个程序，计算卢卡完成交付所需的最少时间。
### 输入格式:
第一行包含两个整数$$N$$和$$M（2≤N≤1000, 2≤M≤10000）$$，交叉口的数量和街道的数量。交叉口编号为1到$$N$$。
第二行包含四个整数$$A、B、K$$和$$G（1≤A、B≤N、0≤K≤1000, 0≤G≤1000)$$.
以下是顺序：
•卢卡起点的十字路口；
•卢卡必须到达的十字路口；
•乔治先生和卢卡先生之间的出发时间差（卢卡先生在乔治先生出发后正好K分钟从十字路口A出发）；
•乔治先生路线上的十字路口数量。
第三行包含$$G$$整数，这是交叉点的标签，先生
乔治会来参观。每对相邻的整数表示他将穿过的街道。那条街将会存在，乔治先生最多一次穿过每一条街。
下面的每一条M线都包含三个整数$$A、B$$和$$L$$，这意味着在交叉点$$A$$和$$B$$之间有一条街道，需要$$L$$分钟才能穿过。我会在1到1000之间。
### 输出格式:
输出$$Luka$$交付所需的最少时间（分钟）。
### 输入样例1:
in
6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15
### 输出样例1:
out
21
### 输入样例2:
in
8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23
### 输出样例2:
out
40
答案：若无答案欢迎评论