问题描述

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

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