import sys
__all__ = ['Road']

class Road(object):
    def __add__(self, lengths):
        return self.insert(*lengths)

    def clear(self):
        self.start = None
        self.end = None
        return self

    def find(self, *lengths):
        return lengths in self

    def __init__(self):
        self.start = None
        self.end = None

    def insert(self, a_len, b_len, c_len=0):
        if self.start is None and self.end is None:
            self.start = start_left, start_right = Node(), Node()
            self.end = end_left, end_right = Node(), Node()
            start_left.next = a_len, end_left
            start_right.next = b_len, end_right
            end_left.sideways = c_len, end_right
            end_right.sideways = c_len, end_left
        else:
            end_left, end_right = self.end
            new_end_left, new_end_right = Node(), Node()
            end_left.next = a_len, new_end_left
            end_right.next = b_len, new_end_right
            new_end_left.sideways = c_len, new_end_right
            new_end_right.sideways = c_len, new_end_left
            self.end = new_end_left, new_end_right
        return self

    def __iter__(self):
        if self.start is None:
            return
        current = start_left, start_right = self.start
        while current != self.end:
            current_left, current_right = current
            a_len, next_left = current_left.next
            b_len, next_right = current_right.next
            c_len, _ = next_left.sideways
            current = next_left, next_right
            yield a_len, b_len, c_len

    def iter_r(self, current_left = None, current_right = None):
        if current_left is None and current_right is None:
            if self.start is None:
                return
            else:
                current_left, current_right = self.start
        if (current_left, current_right) == self.end:
            return
        else:
            a_len, next_left = current_left.next
            b_len, next_right = current_right.next
            c_len, _ = next_left.sideways
            yield a_len, b_len, c_len
            for a,b,c, in self.iter_r(next_left, next_right):
                yield a,b,c

    def load(self, filename):
        self.clear()
        lines = open(filename, 'r')
        sections_num = int(lines.next())
        for x in xrange(0, sections_num-1):
            a = int(lines.next())
            b = int(lines.next())
            c = int(lines.next())
            self.insert(a,b,c)
        a = int(lines.next())
        b = int(lines.next())
        self.insert(a,b)
        return self

    def path(self):
        left_price, right_price = 0, 0
        left_path, right_path = [], []
        current = current_left, current_right = self.start
        while (current_left, current_right) != self.end:
            a_len, next_left = current_left.next
            b_len, next_right = current_right.next
            c_len, _ = next_right.sideways
            if a_len + left_price <= b_len + c_len + right_price:
                new_left_price = left_price + a_len
                new_left_path = left_path[:]
                new_left_path.append('a')
            else:
                new_left_price = right_price + b_len + c_len
                new_left_path = right_path[:]
                new_left_path.append('b')
                new_left_path.append('r')
            if b_len + right_price <= a_len + c_len + left_price:
                new_right_price = right_price + b_len
                new_right_path = right_path[:]
                new_right_path.append('b')
            else:
                new_right_price = left_price + a_len + c_len
                new_right_path = left_path[:]
                new_right_path.append('a')
                new_right_path.append('r')
            left_price = new_left_price
            right_price = new_right_price
            left_path = new_left_path
            right_path = new_right_path
            current_left, current_right = next_left, next_right
        for path in left_path, right_path:
            if path[-1:] == ['r']: path.pop()
        if left_price <= right_price:
            return left_price, ''.join(left_path)
        else:
            return right_price, ''.join(right_path)

    def path_r(self):
        price, path = self._path_r(0, [], 0, [])
        if path[-1:] == ['r']:
            path.pop()
        return price, ''.join(path)

    def _path_r(self, left_price, left_path, right_price, right_path, current_left = None, current_right = None):
        if current_left is None and current_right is None:
            current_left, current_right = self.start
        if (current_left, current_right) == self.end:
            return (left_price, left_path) if left_price <= right_price else (right_price, right_path)
        else:
            a_len, next_left = current_left.next
            b_len, next_right = current_right.next
            c_len, _ = next_right.sideways
            if a_len + left_price <= b_len + c_len + right_price:
                new_left_price = left_price + a_len
                new_left_path = left_path[:]
                new_left_path.append('a')
            else:
                new_left_price = right_price + b_len + c_len
                new_left_path = right_path[:]
                new_left_path.append('b')
                new_left_path.append('r')
            if b_len + right_price <= a_len + c_len + left_price:
                new_right_price = right_price + b_len
                new_right_path = right_path[:]
                new_right_path.append('b')
            else:
                new_right_price = left_price + a_len + c_len
                new_right_path = left_path[:]
                new_right_path.append('a')
                new_right_path.append('r')
        return self._path_r(new_left_price, new_left_path, new_right_price, new_right_path, next_left, next_right)

    def __str__(self):
        if self.start is None:
            return "| empty |"
        else:
            return ''.join("""
             |     |
            %3d   %3d
             |_%3d_| """ % (a, b, c) for a,b,c in self)


class Node(object):
    def __init__(self, next=None, sideways=None):
        self.next = (0, None) if next is None else next
        self.sideways = (0, None) if sideways is None else sideways


if __name__ == '__main__':
    sys.setrecursionlimit(10000000)
    road = Road()
    road.load('test10000_2.txt')