Buggy python submission (verdict: Runtime Error):
from collections import deque
r, c = map(int, raw_input().split())
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]

d = {}
P.sort()
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if r1 == r2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
P.sort(key=lambda (r,c,a): (c,r))
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if c1 == c2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
m = {}
for i, (r0, c0, a0) in enumerate(P):
    m[r0, c0] = (a0, i)

used = [0]*n
for i in xrange(n):
    if not used[i]:
        r0, c0, base = P[i]

        used[i] = 1
        deq = deque()
        deq.append((r0, c0, base))
        rs = {r0: 0}
        cs = {c0: 0}

        while deq:
            r0, c0, now = deq.popleft()

            for (r1, c1), diff in d[r0, c0]:
                a1, j = m[r1, c1]
                if r0 == r1:
                    if not used[j]:
                        cs[c1] = cs[c0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if cs[c0] + diff != cs[c1]:
                            print "No"
                            exit(0)
                else:
                    if not used[j]:
                        rs[r1] = rs[r0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if rs[r0] + diff != rs[r1]:
                            print "No"
                            exit(0)
        rmin = min(rs.values())
        cmin = min(cs.values())
        if rmin + cmin + base < 0:
            print "No"
            exit(0)
print "Yes"

Fixed submission:
from collections import deque
r, c = map(int, raw_input().split())
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]

d = {}
P.sort()
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if r1 == r2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
P.sort(key=lambda (r,c,a): (c,r))
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if c1 == c2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
m = {}
for i, (r0, c0, a0) in enumerate(P):
    m[r0, c0] = (a0, i)
used = [0]*n
for i in xrange(n):
    if not used[i]:
        r0, c0, base = P[i]

        used[i] = 1
        deq = deque()
        deq.append((r0, c0, base))
        rs = {r0: 0}
        cs = {c0: 0}

        while deq:
            r0, c0, now = deq.popleft()

            for (r1, c1), diff in d.get((r0, c0), []):
                a1, j = m[r1, c1]
                if r0 == r1:
                    if not used[j]:
                        cs[c1] = cs[c0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if cs[c0] + diff != cs[c1]:
                            print "No"
                            exit(0)
                else:
                    if not used[j]:
                        rs[r1] = rs[r0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if rs[r0] + diff != rs[r1]:
                            print "No"
                            exit(0)
        rmin = min(rs.values())
        cmin = min(cs.values())
        if rmin + cmin + base < 0:
            print "No"
            exit(0)
print "Yes"