题目描述

魔法师小蓝为了营救自己的朋友小 Q，来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 $N$ 个结点 $M$ 条边的无向图，结点编号为 $0, 1, 2, \dots, N-1$，图中没有重边和自环。敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 $w$，每当小蓝经过一条边时就会受到这条边对应的 $w$ 的伤害。小蓝从结点 $0$ 出发，沿着边行走，想要到达结点 $N-1$ 营救小 $Q$。

小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下 $L$ 条边 $e_1, e_2, ..., e_L$（可以出现重复的边），那么期间小蓝受到的总伤害就是 $P = \displaystyle \sum_{i=1}^{L} w(e_i)$，$w(e_i)$ 表示边 $e_i$ 的伤害属性。如果 $L \geq K$，那么小蓝就可以从这 $L$ 条边当中选出连续出现的 $K$ 条边 $e_c, e_{c+1}, \dots, e_{c+K-1}$ 并免去在这 $K$ 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 $P' = P - \displaystyle \sum_{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$ 受到的最小伤害。

4 2 3
0 1 2
1 2 1
2 3 4

2

2 5 1
0 1 1

0

提示

样例说明

• 样例 $1$，存在路径：$0 \rightarrow 1 \rightarrow 2 \rightarrow 3$，$K = 2$，如果在 $0 \rightarrow 1 \rightarrow 2$ 上使用魔法，那么答案就是 $0 + 0 + 4 = 4$；如果在 $1 \rightarrow 2 \rightarrow 3$ 上使用魔法，那么答案就是 $2 + 0 + 0 = 2$。再也找不到比 $2$ 还小的答案了，所以答案就是 $2$。
• 样例 $2$，存在路径：$0 \rightarrow 1 \rightarrow 0 \rightarrow 1 \rightarrow 0 \rightarrow 1$，$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 \leq 10$，$0 \leq u, v \leq N - 1$，$1 \leq w \leq 1000$。