Problem p03306 (python)

Fixed submission:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    par = [None] * (n + 1)
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                par[z] = (x, dat[y/3*3+2])
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        px = []
        pz = []
        x, z = f
        while x != 1:
            px.append(par[x])
            x = par[x][0]
        while z != 1:
            pz.append(par[z])
            z = par[z][0]
        while px and pz and px[-1] == pz[-1]:
            px.pop()
            pz.pop()
        px += pz[::-1]
        k = [x[1] for x in px]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[f[1]] = z
        pu(f[1])
        while st:
            x = po()
            if dp[x] <= 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    pu(1)
    dp[1] = 0
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            s = dat[y/3*3+2]
            if dp[z] is None:
                dp[z] = s - dp[x]
                pu(z)
            elif dp[z] + dp[x] != s:
                print 0
                return
            y = xt[y]
    x = 1 - min(dp[i] for i in xrange(1, n + 1) if col[i] == 1)
    for i in xrange(1, n + 1):
        if col[i] == 1:
            dp[i] += x
        else:
            dp[i] -= x
    x = min(dp[i] for i in xrange(1, n + 1) if col[i] == 2)
    if x <= 0:
        print 0
    else:
        print x
main()

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m, = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 3 * m))
    la = [None] * (n + 1)
    xt = [None] * (3 * m)
    j = 0
    for i in xrange(m):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    st = [1]
    pu = st.append
    po = st.pop
    col = [0] * (n + 1)
    col[1] = 1
    f = None
    while st:
        x = po()
        y = la[x]
        while y is not None:
            z = dat[y]
            if not col[z]:
                col[z] = col[x] ^ 3
                pu(z)
            elif col[z] == col[x] and f is None:
                f = (x, z)
                s = dat[y/3*3+2]
            y = xt[y]
    dp = [None] * (n + 1)
    if f is not None:
        pu(f[1])
        col = [0] * (n + 1)
        col[f[1]] = 1
        par = [None] * (n + 1)
        while st:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if x == f[1] and z == f[0]:
                    s = dat[y/3*3+2]
                elif not col[z]:
                    col[z] = 1
                    par[z] = (x, dat[y/3*3+2])
                    pu(z)
                y = xt[y]
        k = []
        x, z = f
        while x != z:
            k.append(par[x][1])
            x = par[x][0]
        s += sum(k)
        if s % 2:
            print 0
            return
        z = s / 2 - sum(k[::2])
        dp[x] = z
        pu(z)
        while st:
            x = po()
            if dp[x] < 0:
                print 0
                return
            y = la[x]
            while y is not None:
                z = dat[y]
                s = dat[y/3*3+2]
                if dp[z] is None:
                    dp[z] = s - dp[x]
                    pu(z)
                elif dp[z] + dp[x] != s:
                    print 0
                    return
                y = xt[y]
        print 1
        return
    col = [0] * (n + 1)
    pu(1)
    while st:
        x = po()
        if not col[x]:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        else:
            lo, hi = 1, 1001001001
            col[x] = 2
            y = la[x]
            while y is not None:
                z = dat[y]
                if col[z] == 2:
                    s = dat[y/3*3+2]
                    l, h = s - dp[z][1], s - dp[z][0]
                    if lo < l:
                        lo = l
                    if hi > h:
                        hi = h
                y = xt[y]
            dp[x] = (lo, hi)
    ans = dp[1][1] - dp[1][0] + 1
    if ans < 0:
        ans = 0
    print ans
main()