Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Lightning McQueen chuẩn bị cùng đội đua của mình tham gia một giải đua lớn. Giải đua được tổ chức ở một đất nước có n thành phố. Giữ 2 thành phố khác nhau luôn tồn tại một con đường nối trực tiếp 2 chiều.

Cuộc thi diễn ra tất cả là r round. Round thứ i sẽ là cuộc đua từ thành phố s[i] tới thành phố t[i]. McQueen có thể thay đổi lốp của mình nhưng không quá k[i] lần. Việc thay đổi lốp sẽ diễn ra ở các thành phố và sẽ không tốn chút thời gian nào cả. Một loại lốp có thể được sử dụng nhiều lần trong một round nhưng tổng số lần thay đổi lốp vẫn sẽ không quá k[i] lần. McQueen có thể tự do lựa chọn đường đi cho mình.

Trước khi đi thi, Mater – bạn thân của McQueen đã lựa chọn sẵn ra m loại lốp, mỗi loại lốp khi đi trên mỗi con đường khác nhau thì sẽ có thời gian đi là khác nhau.

McQueen thì đang bận tập trung rèn luyện kĩ năng lái xe của mình còn Mater thì lại quá thật thà và cố phần hơi ngốc nghếch trong việc lựa chọn chiến lược đua phù hợp với m loại lốp đã chọn.

Các bạn hãy giúp McQueen và Mater chiến thắng nhé!

Input

Dòng đầu tiên gồm 3 số nguyên n, m, r (1 <= n, m <= 60, 1 <= r <= 10^5) lần lượt là số thành phố, số loại lốp mà Mater đã chọn và só round của cuộc đua.

Tiếp theo mà m ma trận kích thước n * n.

Với mỗi ma trận I, ô (p, q) cho biết thời gian đi đường từ thành phố p đến thành phố q nếu McQueen sử dụng loại lốp I là bao nhiêu. Thời gian di chuyển là số nguyên không âm và không quá 10^6.

r dòng tiếp theo, dòng thứ I gồm 3 số nguyên s[i], t[i], k[i] cho biết round i sẽ có thành phố xuất phát là s[i] và thành phố cuối là t[i] và số lần đổi lốp không quá k[i] lần (1 <= s[i], t[i] <= n, s[i] != t[i], 1 <= k[i] <= 1000)

Output

Gồm r dòng, mỗi dòng là thời gian ngắn nhất mà McQueen có thể hoàn thành chặng đua.

Example

Input:
3 2 1
0 0 9
9 0 9
9 9 0
0 9 9
9 0 1
9 9 0
1 3 2

Output:
1