题目描述
魔法师小蓝为了营救自己的朋友小 Q，来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 N 个结点 M 条边的无向图，结点编号为 0, 1, 2, . . . , N−1，图中没有重边和自环。敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 w，每当小蓝经过一条边时就会受到这条边对应的 w 的伤害。小蓝从结点 0出发，沿着边行走，想要到达结点 N−1 营救小 Q。
小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下L 条边：e1, e2, . . . , eL（可以出现重复的边），那么期间小蓝受到的总伤害就是P =
∑Li=1 w(ei)，w(ei) 表示边 ei 的伤害属性。如果L≥K，那么小蓝就可以从这 L条边当中选出连续出现的K条边 ec , ec+1, . . . , ec+K−1并免去在这K 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 P
′ = P −∑c+K−1i=cw(ei)。
注意必须恰好选出连续出现的 K 条边，所以当 L < K 时无法使用魔法。
小蓝最多只可以使用一次上述的魔法，请问从结点 0 出发到结点 N − 1 受到的最小伤害是多少？题目保证至少存在一条从结点 0 到 N − 1 的路径。
输入格式
第一行输入三个整数，N, K, M，用空格分隔。
接下来 M 行，每行包含三个整数 u, v,w，表示结点 u 与结点 v 之间存在一条伤害属性为 w 的无向边。
输出格式
输出一行，包含一个整数，表示小蓝从结点 0 到结点 N − 1 受到的最小伤害。
样例输入
4 2 3 0 1 2 1 2 1 2 3 4
样例输出
2
提示
样例 1，存在路径：0 → 1 → 2 → 3，K = 2，如果在 0 → 1 → 2 上使用魔法，那么答案就是 0 + 0 + 4 = 4；如果在 1 → 2 → 3 上使用魔法，那么答案就是 2 + 0 + 0 = 2。再也找不到比 2 还小的答案了，所以答案就是 2。
样例 2，存在路径：0 → 1 → 0 → 1 → 0 → 1，K = 5，这条路径总计恰好走了 5 条边，所以正好可以用魔法消除所有伤害，答案是 0。
对于 30% 的评测用例，1 ≤ N ≤ 20。
对于 50% 的评测用例，1 ≤ N ≤ 100。
对于 100% 的评测用例，1 ≤ N ≤ 1000, 1 ≤ M ≤
N×(N−1)/2，1 ≤ K ≤ 10，0 ≤ u, v ≤ N − 1，1 ≤ w ≤ 1000
比赛公告
为CSP考试而出题,应对接下来的各种情况
----------------------------------------------------------------------------------------------------------