Quản trị viên mạng của một công ty cần phân tích trạng thái hiện tại của mạng lưới truyền thông toàn cầu của họ. Mạng lưới truyền thông bao gồm các máy chủ và các liên kết cáp giữa những máy chủ này, mỗi liên kết có một chi phí. Một k-route là một chuỗi gồm k + 1 máy chủ khác nhau, trong đó hai máy chủ liên tiếp được kết nối bằng một liên kết cáp. Một chu trình là một k-route (đối với bất kỳ k > 1) sao cho máy chủ bắt đầu và máy chủ kết thúc được kết nối bởi một liên kết cáp. Mạng lưới truyền thông không chứa chu trình. Chi phí của một k-route là tổng chi phí của các liên kết giữa hai máy chủ liên tiếp trong k-route đó. Một trong những chỉ số của phân tích là k-route có chi phí tối thiểu của mạng lưới cho giá trị k cho trước. k-route có chi phí tối thiểu của mạng lưới truyền thông trong ví dụ là 6-1-4 với chi phí 3. Cho mạng lưới truyền thông G và một giá trị nguyên k, hãy giúp quản trị viên mạng tìm k-route có chi phí tối thiểu của G.

Đầu vào

Đầu vào bao gồm các dòng sau:

• Dòng 1: chứa hai số nguyên n và k (1 ≤ n ≤ 10000, 1 ≤ k ≤ 2000), trong đó n là số lượng máy chủ của mạng lưới truyền thông G (các máy chủ được đánh số 1, 2, ..., n).
• Dòng 2: chứa một số nguyên m (1 ≤ m ≤ 10000) là số lượng liên kết cáp giữa các máy chủ của G.
• Dòng i + 2: chứa ba số nguyên u, v và w: u và v là hai điểm cuối của liên kết thứ i của G (với 1 ≤ i ≤ m), w là chi phí của liên kết này.

Đầu ra

Đầu ra chứa chi phí của k-route đã tìm thấy

Ví dụ:

Input:

6 2
5
1 2 4
1 4 1
1 5 3
1 6 2
2 3 1

Ouput:

3