#!/usr/bin/python
# -*- coding: utf-8 -*-
from tkinter import *


class Container(object):
    def __init__(self, mode='queue'):
        self.__mode = mode
        self.__container = []

    def get(self):
        if self.__mode == 'stack':
            return self.__container.pop()
        if self.__mode == 'priqueue':
            self.__container.sort(key=lambda x: (x['f'], x['id']))
        return self.__container.pop(0)

    def put(self, item):
        self.__container.append(item)

    def empty(self):
        return len(self.__container) == 0

    def contains(self, item):
        try:
            self.__container.index(item)
        except ValueError:
            return False
        return True


def xfs(graph, start, end, container):
    shortest_path = []
    visited_nodes = []

    container.put(start)
    while not container.empty():
        curr = container.get()

        curr['visited'] = True
        visited_nodes.append(curr['id'])

        for succs in curr['successors']:
            succs_node = graph[succs['id']]
            if not succs_node['visited']:
                succs_node['back'] = curr['id']

                if succs_node is end:
                    visited_nodes.append(succs_node['id'])

                    while succs_node['back'] is not None:
                        shortest_path.append(succs_node['id'])
                        succs_node = graph[succs_node['back']]
                    shortest_path.append(start['id'])
                    shortest_path.reverse()
                    return visited_nodes, shortest_path

                container.put(succs_node)

    return visited_nodes, shortest_path


def search(graph, start, end, container, func):
    shortest_path = []
    visited_nodes = []

    start['f'] = func(start['g'], start['h'])
    container.put(start)

    while not container.empty():
        curr = container.get()

        visited_nodes.append(curr['id'])
        curr['visited'] = True

        # Reach the goal
        if curr is end:
            break

        # Loop over successors of current node
        for succs in curr['successors']:
            succs_node = graph[succs['id']]
            fn = succs_node['f']
            fm = func(curr['g'] + succs['w'], succs_node['h'])

            if succs_node['visited'] and fm >= fn:
                continue

            if fm < fn:
                succs_node['g'] = curr['g'] + succs['w']
                succs_node['f'] = fm
                succs_node['back'] = curr['id']

                if not container.contains(succs_node):
                    container.put(succs_node)

    if curr is end:
        while curr['back'] is not None:
            shortest_path.append(curr['id'])
            curr = graph[curr['back']]
        shortest_path.append(start['id'])
        shortest_path.reverse()

    return visited_nodes, shortest_path


def problem_1(input_file):
    graph = {}
    with open(input_file, 'r') as f:
        num_nodes = int(f.readline())
        start_idx, end_idx = f.readline().strip('\r\n').rstrip(' ').split(' ')

        for i in range(num_nodes):
            graph[i] = {
                'id': i,
                'successors': [],
                'visited': False,
                'back': None,
                'f': 1000000009.,
                'g': 0.
            }
            for j, w in enumerate(f.readline().strip('\r\n').rstrip(' ').split(' ')):
                w = float(w)
                if w > 0:
                    graph[i]['successors'].append({
                        'id': j,
                        'w': w
                    })

        for i, v in enumerate(f.readline().strip('\r\n').rstrip(' ').split(' ')):
            graph[i]['h'] = float(v)

    visited, shortest_path = xfs(graph=graph, start=graph[int(start_idx)], end=graph[int(end_idx)],
                                 container=Container('stack'))
    # visited, shortest_path = search(graph=graph, start=graph[int(start_idx)], end=graph[int(end_idx)],
    #                                 container=Container('priqueue'),
    #                                 func=lambda g, h: g + h)
    print(visited)
    print(shortest_path)


class GUI(Frame):
    def __init__(self, master=None):
        super().__init__(master)


def problem_2():
    master = Tk()
    window = GUI(master=master)
    window.mainloop()
    master.destroy()


def main():
    problem_1(input_file='input.txt')
    # problem_2()


if __name__ == '__main__':
    main()