Problem p02587 (python)

Fixed submission:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def search_next(l, r, SC):
    ll, lc = l
    rr, rc = r
    nexts = []
    if len(ll) > len(rr):
        part = ll[::-1]
        for s,c in SC:
            if s[-len(part):] == part:
                r_n = (s[:-len(ll)], rc + c)
                l_n = ('', lc)
                nexts.append((rc+c+lc, (l_n, r_n)))
            elif s == part[-len(s):]:
                l_n =(ll[len(s):], lc)
                r_n = ('', rc + c)
                nexts.append((rc + c + lc, (l_n, r_n)))
    else:
        part = rr[::-1]
        for s, c in SC:
            if s[:len(part)] == part:
                l_n = (s[len(rr):], lc + c)
                r_n = ('', rc)
                nexts.append((lc+rc+c, (l_n, r_n)))
            elif s == part[:len(s)]:
                r_n = (rr[:-len(s)], rc)
                l_n = ('', lc + c)
                nexts.append((lc + rc + c, (l_n, r_n)))
    return nexts

def palindrome(l, r):
    if l + r == (l+r)[::-1]:
        return True
    else:
        return False



def run():
    totalL = 0
    N = int(sysread())
    SC = []
    for i in range(N):
        s,c = input().split()
        c = int(c)
        SC.append((s,c))
        totalL += len(s)

    min_val = INF
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False
        count = 0
        while queue:
            count += 1
            if count > 200000:break
            #print(queue)
            cost, (l, r) = heappop(queue)
            if palindrome(l[0], r[0]):
                done = True
                #print(l, r)
                break
            nexts = search_next(l, r, SC)
            for n in nexts:
                heappush(queue, n)
        if done:
            min_val = min(min_val, cost)
    if min_val == INF:
        print(-1)
    else:
        print(min_val)

if __name__ == "__main__":
    run()

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def search_next(l, r, SC):
    ll, lc = l
    rr, rc = r
    nexts = []
    if len(ll) > len(rr):
        part = ll[len(rr):][::-1]
        for s,c in SC:
            if s[-len(part):] == part:
                r_n = ((s + rr)[:-len(ll)], rc + c)
                l_n = (0, lc)
                nexts.append((rc+c+lc, (l_n, r_n)))
            elif s in part:
                tmp = s + rr
                l_n =(ll[len(tmp):], lc)
                r_n = (0, rc + c)
                nexts.append((rc + c + lc, (l_n, r_n)))
    else:
        part = rr[:-len(ll)][::-1]
        for s, c in SC:
            if s[:len(part)] == part:
                l_n = ((ll + s)[len(rr):], lc + c)
                r_n = (0, rc)
                nexts.append((lc+rc+c, (l_n, r_n)))
            elif s in part:
                r_n = (rr[:-len(ll)-len(s)], rc)
                l_n = (0, lc + c)
                nexts.append((lc + rc + c, (l_n, r_n)))
    return nexts

def palindrome(l, r):
    if len(l+r) > 1 and l + r == (l+r)[::-1]:
        return True
    else:
        return False



def run():
    totalL = 0
    N = int(sysread())
    SC = []
    for i in range(N):
        s,c = input().split()
        c = int(c)
        SC.append((s,c))
        totalL += len(s)

    min_val = INF
    for s,c in SC:
        queue = []
        left = (s, c)
        right = ('', 0)
        heappush(queue, (c, (left, right)))
        done = False
        while queue:
            #print(queue)
            cost, (l, r) = heappop(queue)
            if palindrome(l[0], r[0]):
                done = True
                break
            nexts = search_next(l, r, SC)
            for n in nexts:
                heappush(queue, n)
        if done:
            min_val = min(min_val, cost)
    if min_val == INF:
        print(-1)
    else:
        print(min_val)

if __name__ == "__main__":
    run()