Đua xe AlgoRace

Có một cuộc đua xe diễn ra ở một đất nước gồm $n$ thành phố, đánh số từ $1$ đến $n$. Giữa hai thành phố phân biệt bất kỳ đều có đúng một con đường hai chiều nối trực tiếp.

Ban tổ chức chuẩn bị $m$ loại xe khác nhau. Mỗi loại xe đi qua mỗi con đường (theo mỗi chiều) trong một khoảng thời gian riêng: loại xe $i$ đi từ thành phố $j$ tới thành phố $k$ mất một thời gian cho trước. Thời gian đi từ $j$ tới $k$ và từ $k$ tới $j$ có thể khác nhau (ma trận thời gian không nhất thiết đối xứng).

Cuộc đua gồm $r$ vòng. Ở vòng thứ $i$, tay đua xuất phát tại thành phố $s_i$ và cần về đích tại thành phố $t_i$. Trong một vòng, tay đua được phép đổi xe không quá $k_i$ lần. Việc đổi xe có thể thực hiện tại bất kỳ thành phố nào và không tốn thời gian. Một loại xe có thể được dùng nhiều lần, nhưng tổng số lần đổi không vượt quá $k_i$. Tay đua tự do chọn đường đi tới đích.

Với mỗi vòng, hãy tìm thời gian nhỏ nhất để hoàn thành.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $r$.
• Tiếp theo là $m$ khối, mỗi khối là một ma trận $n\times n$ mô tả một loại xe. Số thứ $k$ trên dòng thứ $j$ của khối thứ $i$ là thời gian loại xe $i$ đi từ thành phố $j$ tới thành phố $k$. Đường chéo luôn bằng $0$.
• $r$ dòng cuối, mỗi dòng chứa ba số nguyên $s_i$, $t_i$, $k_i$: thành phố xuất phát, thành phố đích và số lần đổi xe tối đa của vòng thứ $i$.

Dữ liệu ra

In ra $r$ dòng, dòng thứ $i$ là thời gian nhỏ nhất để hoàn thành vòng thứ $i$.

Ràng buộc

• $2\le n\le 60$
• $1\le m\le 60$
• $1\le r\le {10}^5$
• Mọi thời gian trên đường là số nguyên trong đoạn $[0,{10}^6]$.
• $1\le s_i,t_i\le n$, $s_i\ne t_i$, $0\le k_i\le 1000$

Ví dụ