THỰC HÀNH

            Cho đơn đồ thị có hướng (không có khuyên) trọng số dương G có N đỉnh. Đồ thị G được cho bởi ma trận kề A = (a_ij), trong đó:

• a_ij > 0 là trọng số của cung đi từ đỉnh i đến đỉnh j.
• a_ij = 0 nếu không có cung đi từ đỉnh i đến đỉnh j.

Yêu cầu: Hãy tìm đường đi ngắn nhất qua đúng K cạnh của đồ thị. Tức là tìm ma trận C = (c_ij), trong đó:

• c_ij = 0 nếu không có đường đi từ i đến j qua đúng K cạnh của đồ thị.
• c_ij > 0 là độ dài đường đi ngắn nhất từ i đến j qua đúng K cạnh của đồ thị.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương N, K.
• N dòng sau, dòng thứ i chứa N số nguyên không âm a_i1, a_i2, …, a_iN.

Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

Gồm N dòng, dòng thứ i chứa N số nguyên không âm c_i1, c_i2, …, c_iN. Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:
4 2
0 1 0 0
0 0 1 3
3 0 0 1
1 0 0 0

Dữ liệu ra:
0 0 2 4
4 0 0 2
2 4 0 0
0 2 0 0

Giới hạn: 1 ≤ K ≤ N ≤ 200; 0 ≤ a_ij ≤ 1000.