### 问题描述 魔法师小蓝为了营救自己的朋友小 $Q$，来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 $N$ 个结点 $M$ 条边的无向图，结点编号为 $0,1,2,...,N-1$，图中没有重边和自环。敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 $w$，每当小蓝经过一条边时就会受到这条边对应的 $w$ 的伤害。小蓝从结点 $0$ 出发，沿着边行走，想要到达结点 $N-1$ 营救小 $Q$。 小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下 $L$ 条边：$e_1,e_2,...,e_L$ （可以出现重复的边），那么期间小蓝受到的总伤害就是 $P=\sum\limits_{i=1}^L w(e_i)$，$w(e_i)$ 表示边 $e_i$ 的伤害属性。如果 $L \geq K$，那么小蓝就可以从这 $L$ 条边当中选出连续出现的 $K$ 条边 $e_c,e_{c+1},...,e_{c+K-1}$ 并免去在这 $K$ 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 $P' = P - \sum\limits_{i=c}^{c+K-1} w(e_i)$。注意必须恰好选出连续出现的 $K$ 条边，所以当 $L < K$ 时无法使用魔法。 小蓝最多只可以使用一次上述的魔法，请问从结点 $0$ 出发到结点 $N-1$ 受到的最小伤害是多少？题目保证至少存在一条从结点 $0$ 到 $N-1$ 的路径。 ### 输入格式 第一行输入三个整数，$N,K,M$，用空格分隔。接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示结点 $u$ 与结点 $v$ 之间存在一条伤害属性为 $w$ 的无向边。 ### 输出格式 输出一行，包含一个整数，表示小蓝从结点 $0$ 到结点 $N-1$ 受到的最小伤害。 ### 样例输入1 ```text 4 2 3 0 1 2 1 2 1 2 3 4 ``` ### 样例输出1 ```text 2 ``` ### 样例输入2 ```text 2 5 1 0 1 1 ``` ### 样例输出2 ```text 0 ``` ### 样例说明 样例 $1$，存在路径：$0\to1\to2\to3$，$K=2$，如果在 $0\to1\to2$ 上使用魔法，那么答案就是 $0+0+4=4$；如果在 $1\to2\to3$ 上使用魔法，那么答案就是 $2+0+0=2$。再也找不到比 $2$ 还小的答案了，所以答案就是 $2$。 样例 $2$，存在路径：$0\to1\to0\to1\to0\to1$，$K=5$，这条路径总计恰好走了 $5$ 条边，所以正好可以用魔法消除所有伤害，答案是 $0$。 ### 评测用例规模与约定 对于 $30$% 的评测用例，$1\leq N \leq 20$。 对于 $50$% 的评测用例，$1\leq N \leq 100$。 对于 $100$% 的评测用例，$1\leq N \leq 1000$，$1\leq M \leq \frac{N\times(N-1)}{2}$，$1\leq K\leq10$，$0\leq u,v\leq N-1$，$1\leq w\leq 1000$。