魔法師小藍(lán)為了營救自己的朋友小 Q，來到了敵人布置的魔法陣。魔法陣可以看作是一幅具有 N 個(gè)結(jié)點(diǎn) M 條邊的無向圖，結(jié)點(diǎn)編號(hào)為 0, 1, 2, . . . , N?1，圖中沒有重邊和自環(huán)。敵人在每條邊上都布置了陷阱，每條邊都有一個(gè)傷害屬性 w，每當(dāng)小藍(lán)經(jīng)過一條邊時(shí)就會(huì)受到這條邊對應(yīng)的 w 的傷害。小藍(lán)從結(jié)點(diǎn) 0出發(fā)，沿著邊行走，想要到達(dá)結(jié)點(diǎn) N?1 營救小 Q。

小藍(lán)有一種特殊的魔法可以使用，假設(shè)一條路徑按照順序依次經(jīng)過了以下L 條邊：e₁, e₂, . . . , e_L（可以出現(xiàn)重復(fù)的邊），那么期間小藍(lán)受到的總傷害就是P = ∑^L_i=1 w(e_i)，w(e_i) 表示邊 e_i 的傷害屬性。如果L≥K，那么小藍(lán)就可以從這 L條邊當(dāng)中選出連續(xù)出現(xiàn)的K條邊 e_c , e_c+1, . . . , e_c+K?1并免去在這K 條邊行走期間所受到的傷害，即使用魔法之后路徑總傷害變?yōu)?P ′ = P ?∑^c+K?1_i=cw(e_i)。

注意必須恰好選出連續(xù)出現(xiàn)的 K 條邊，所以當(dāng) L < K 時(shí)無法使用魔法。

小藍(lán)最多只可以使用一次上述的魔法，請問從結(jié)點(diǎn) 0 出發(fā)到結(jié)點(diǎn) N ? 1 受到的最小傷害是多少？題目保證至少存在一條從結(jié)點(diǎn) 0 到 N ? 1 的路徑。

第一行輸入三個(gè)整數(shù)，N, K, M，用空格分隔。

接下來 M 行，每行包含三個(gè)整數(shù) u, v,w，表示結(jié)點(diǎn) u 與結(jié)點(diǎn) v 之間存在一條傷害屬性為 w 的無向邊。

輸出一行，包含一個(gè)整數(shù)，表示小藍(lán)從結(jié)點(diǎn) 0 到結(jié)點(diǎn) N ? 1 受到的最小傷害。

樣例 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，這條路徑總計(jì)恰好走了 5 條邊，所以正好可以用魔法消除所有傷害，答案是 0。

對于 30% 的評(píng)測用例，1 ≤ N ≤ 20。

對于 50% 的評(píng)測用例，1 ≤ N ≤ 100。

對于 100% 的評(píng)測用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N?1)/2，1 ≤ K ≤ 10，0 ≤ u, v ≤ N ? 1，1 ≤ w ≤ 1000