Có một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, mỗi cạnh có một giá trị sát thương $w$.

Lan phải đi từ đỉnh $0$ đến đỉnh $N-1$; cậu có thể dùng phép thuật để xóa sát thương của tối đa $K$ cạnh liên tiếp (tức là sát thương của $K$ cạnh này không tính vào tổng sát thương).

Hãy tìm tổng sát thương nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên $N$, $K$, $M$, lần lượt biểu thị số đỉnh, số cạnh có thể xóa sát thương và số cạnh.

Tiếp theo là $M$ dòng, mỗi dòng gồm ba số nguyên $u$, $v$, $w$, biểu thị một cạnh.

Dữ liệu ra

In ra một số nguyên, là tổng sát thương nhỏ nhất.

Ví dụ 1

Input

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

Output

2

Ví dụ 2

Input

2 5 1
0 1 1

Output

0

Ghi chú

Giải thích ví dụ

Có thể xóa sát thương của các cạnh $0-1$ và $1-2$, tổng sát thương là $1$.

Hoặc xóa sát thương của các cạnh $1-2$ và $2-3$, tổng sát thương là $2$.

Tổng sát thương nhỏ nhất là $1$.

Phạm vi dữ liệu

• $2 \le N \le 100$
• $0 \le K \le 10$
• $1 \le M \le 500$
• $1 \le w \le 1000$