Problem:
 Score : 900 points    Problem Statement AtCoDeer the deer wants a directed graph that satisfies the following conditions:   The number of vertices, N , is at most 300 .  There must not be self-loops or multiple edges.  The vertices are numbered from 1 through N .  Each edge has either an integer weight between 0 and 100 (inclusive), or a label X or Y .  For every pair of two integers (x,y) such that 1 ≤ x ≤ A , 1 ≤ y ≤ B ,
    the shortest distance from Vertex S to Vertex T in the graph where the edges labeled X have the weight x and the edges labeled Y have the weight y , is d_{x,y} .   Construct such a graph (and a pair of S and T ) for him, or report that it does not exist.
Refer to Output section for output format.      Constraints  1  ≤  A,B  ≤  10  1  ≤  d_{x,y}  ≤  100 ( 1  ≤  x  ≤  A , 1  ≤  y  ≤  B )  All input values are integers.         Input Input is given from Standard Input in the following format:  A  B  d_{1,1}  d_{1,2}  ..  d_{1,B}  d_{2,1}  d_{2,2}  ..  d_{2,B}  :  d_{A,1}  d_{A,2}  ..  d_{A,B}       Output If no graph satisfies the condition, print Impossible .  If there exists a graph that satisfies the condition, print Possible in the first line.
Then, in the subsequent lines, print the constructed graph in the following format:  N  M  u_1  v_1  c_1  u_2  v_2  c_2 : u_M  v_M  c_M  S  T   Here, M is the number of the edges, and u_i , v_i , c_i represent edges as follows: there is an edge from Vertex u_i to Vertex v_i whose weight or label is c_i .  Also refer to Sample Outputs.        Sample Input 1 2 3
1 2 2
1 2 3      Sample Output 1 Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3       Sample Input 2 1 3
100 50 1      Sample Output 2 Impossible

Solution (Python):
a, b = map(int, input().split())
distances = [list(map(int, input().split())) for _ in range(a)]
n = 202
m = 0
g = [[] for _ in range(n)]
for i in range(100):
    g[i].append((i + 1, 'X'))
    m += 1
for i in range(100):
    g[i + 101].append((i + 102, 'Y'))
    m += 1
for p in range(0, 101):
    for q in range(0, 101):
        r = -10000000
        for i in range(a):
            for j in range(b):
                r = max(r, distances[i][j] - p * (i + 1) - q * (j + 1))
        if r >= 0:
            g[p].append((n - q - 1, r))
            m += 1
for i in range(a):
    for j in range(b):
        d = [float('inf')] * n
        d[0] = 0
        s = [0]
        while s:
            p = s.pop()
            for to, dist in g[p]:
                if dist == 'X':
                    dist = i + 1
                elif dist == 'Y':
                    dist = j + 1
                s.append(to)
                d[to] = min(d[to], d[p] + dist)
        if d[-1] != distances[i][j]:
            print('Impossible')
            exit(0)
print('Possible')
print(n, m)
for i in range(n):
    for node, dist in g[i]:
        print(i + 1, node + 1, dist)
print(1, n)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def impossible():
    print("Impossible")
    exit()

def main():
    h, w = map(int, input().split())
    t = [list(map(int, input().split())) for _ in range(h)]
    edge = [[0] * 101 for _ in range(101)]

    
    for n_x in range(101):
        for n_y in range(101):
            cost = 0
            for i in range(h):
                for j in range(w):
                    x, y = i + 1, j + 1
                    cur_cost = t[i][j] - x * n_x - y * n_y
                    if cur_cost > cost: cost = cur_cost
            edge[n_x][n_y] = cost
    

    
    for i in range(h):
        for j in range(w):
            x, y = i + 1, j + 1
            tij = t[i][j]
            min_dist = 1000
            for n_x in range(101):
                for n_y in range(101):
                    dist = x * n_x + y * n_y + edge[n_x][n_y]
                    if dist < min_dist: min_dist = dist
            if tij != min_dist: impossible()

    print("Possible")
    print(202, 101 * 101 + 200)
    for u in range(1, 101):
        print(u, u + 1, "X")
    for u in range(102, 202):
        print(u, u + 1, "Y")
    for n_x in range(101):
        for n_y in range(101):
            print(n_x + 1, 202 - n_y, edge[n_x][n_y])
    print(1, 202)

main()

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

"""
ax + by + c という距離をたくさん作れる
全ての(a,b)に対して作るとしてよい（cを大きくすれば無視できるので）
悪さをしない範囲の最小のcを選ぶ
それで上手くいっているかを検証
"""

U = 100
A,B = map(int,input().split())
D = np.array([input().rstrip().split() for _ in range(A)], dtype=np.int64)

ax = np.arange(U+1)[:,None] * np.arange(1,A+1)[None,:] 
by = np.arange(U+1)[:,None] * np.arange(1,B+1)[None,:] 
axby = ax[:,:,None,None] + by[None,None,:,:] 

c = (D[None,:,None,:] - axby).max(axis = 3).max(axis = 1) 
c *= (c > 0)

D2 = (axby + c[:,None,:,None]).min(axis = 2).min(axis = 0) 

if (D != D2).any():
    print('Impossible')
    exit()



graph = []
for a in range(U+1):
    for b in range(U+1):
        graph.append((1+a, (U+2) + b, c[a,b]))
for a in range(U):
    graph.append((a+1,a+2,'X'))
for b in range(U,0,-1):
    graph.append((U+2+b,U+1+b,'Y'))

start = 1
goal = U+2

print('Possible')
print(2*(U+1), len(graph))
for e in graph:
    print(*e)
print(start,goal)

Solution (Python):



def solve(x_max, y_max, d):

    c_table = [[-1] * 100 for _ in range(100)]

    for a in range(100):
        c_table_a = c_table[a]
        for x in range(x_max):
            ax = a * (x + 1)
            dx = d[x]
            for b in range(100):
                c = -1
                for y in range(y_max):
                    c = max(c, dx[y] - ax - b * (y + 1))
                c_table_a[b] = max(c_table_a[b], c)

    ab_max = 0
    c_set = {}
    for x in range(x_max):
        dx = d[x]
        for y in range(y_max):
            dxy = d[x][y]
            f = False
            for a in range(100):
                c_table_a = c_table[a]
                ax = a * (x + 1)
                for b in range(100):
                    if dxy == ax + b * (y + 1) + c_table_a[b]:
                        ab_max = max(ab_max, a, b)
                        c_set[(a, b)] = c_table_a[b]
                        f = True
                        break
                if f: break
            if not f:
                print('Impossible')
                return


    print('Possible')
    print('{} {}'.format((ab_max + 1) * 2, ab_max * 2 + len(c_set)))
    for i in range(ab_max):
        print('{} {} X'.format(i + 1, i + 2))
    for i in range(ab_max):
        print('{} {} Y'.format(ab_max + i + 3, ab_max + i + 2))
    for k, c in c_set.items():
        print('{} {} {}'.format(k[0] + 1, k[1] + ab_max + 2, c))
    print('{} {}'.format(1, ab_max + 2))


def main():
    A, B = input().split()
    A = int(A)
    B = int(B)
    d = [list(map(int, input().split())) for _ in range(A)]

    solve(A, B, d)


if __name__ == '__main__':
    main()

Solution (Python):

A, B = map(int, input().split())
D = [list(map(int, input().split())) for i in range(A)]

N = 101
F = [[0]*N for i in range(N)]
for a in range(N):
    for b in range(N):
        res = 0
        for x in range(A):
            for y in range(B):
                res = max(res, D[x][y] - (x+1)*a - (y+1)*b)
        F[a][b] = res

for x in range(A):
    for y in range(B):
        v = 101
        for a in range(N):
            for b in range(N):
                v = min(v, (x+1)*a + (y+1)*b + F[a][b])
        if v != D[x][y]:
            print("Impossible")
            exit(0)
print("Possible")
print(2*N, N**2 + 2*(N-1))
for i in range(N-1):
    print(i+1, i+2, "X")
    print(103+i, 102+i, "Y")
for a in range(N):
    for b in range(N):
        print(a+1, 102+b, F[a][b])
print(1, 102)

Solution (Python):

A, B = map(int, input().split())
D = [list(map(int, input().split())) for i in range(A)]

N = 101
F = [[0]*N for i in range(N)]
for a in range(N):
    for b in range(N):
        res = 0
        for x in range(A):
            for y in range(B):
                res = max(res, D[x][y] - (x+1)*a - (y+1)*b)
        F[a][b] = res

for x in range(A):
    for y in range(B):
        v = 101
        for a in range(N):
            for b in range(N):
                v = min(v, (x+1)*a + (y+1)*b + F[a][b])
        if v != D[x][y]:
            print("Impossible")
            exit(0)
print("Possible")
print(2*N, N**2 + 2*(N-1))
ans = 0
for i in range(N-1):
    print(i+1, i+2, "X")
    print(103+i, 102+i, "Y")
    ans += 2
for a in range(N):
    for b in range(N):
        ans += 1
        print(a+1, 102+b, F[a][b])
print(1, 102)