import math
import copy
from pprint import pprint

def read_from_file():
    file = open("input.txt", "r")
    first_line = file.readline()
    raza = int(first_line)
    # print("Raza este: {} ".format(raza))

    second_line = file.readline()
    greutate = int(second_line)
    # print("Greutatea broscutei este: {}".format(greutate))

    third_line = file.readline().rstrip()
    start = third_line
    # print("Id-ul frunzei de start: {}".format(start))

    # pentru fiecare frunza avem un dictionar in care ii punem caracteristicile
    # cheia este reprezentata de id si valoarea de o lista cu celelalte caracteristici
    frunze = []
    coordonate = {}
    greutati = {}
    nr_insecte = {}
    for line in file.readlines():
        line = line.split()
        frunze.append(line[0])
        coordonate[line[0]] = (int(line[1]), int(line[2]))
        nr_insecte[line[0]] = int(line[3])
        greutati[line[0]] = int(line[4])

    return raza, greutate, start, frunze, coordonate, nr_insecte, greutati;


class Frunza:
    def __init__(self, id, coordonate, nr_insecte, greutate_actuala, frunza_parinte):
        self.id = id
        self.coordonate = coordonate
        self.nr_insecte = nr_insecte
        self.greutate_actuala = greutate_actuala
        self.frunza_parinte = frunza_parinte

    def obtineDrum(self):
        drum = [self.id]
        frunza = self
        while frunza.frunza_parinte is not None:
            drum.insert(0, frunza.frunza_parinte.id)
            frunza = frunza.frunza_parinte
        return drum

    def contineInDrum(self, frunza_noua_id):
        frunza = self
        while frunza is not None:
            if frunza.id == frunza_noua_id:
                return True
            frunza = frunza.frunza_parinte
        return False

    def __repr__(self):
        sir = "Broscuta cu id-ul "
        sir += self.id
        return sir

    def afisDrum(self):  # returneaza si lungimea drumului
        l = self.obtineDrum()
        sir = ""
        sir += (("->").join(l))
        return sir

    def costNodCurent(self):
        parinte = self.frunza_parinte
        cost_total = 0
        while parinte is not None:
            cost = 0
            drum = self.obtineDrum()
            for frunza in drum:
                cost += 1
                cost -= self.nr_insecte[frunza]
            cost_total += cost
            parinte = parinte.frunza_parinte
        return cost_total


def calculLungime(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)


class Graph:
    # start va fi id-ul frunzei initiale pe care se afla broscuta
    # greutate va fi greutatea broscutei
    # raza = raza lacului
    # dictionarul de frunze

    def __init__(self, raza, start, greutate_initiala, frunze, coordonate, nr_insecte, greutati):
        self.raza = raza
        self.start = start
        self.greutate = greutate_initiala
        self.frunze = frunze
        self.coordonate = coordonate
        self.nr_insecte = nr_insecte
        self.greutati = greutati

    def genereazaSuccesori(self, frunzaCurenta):
        listaSuccesori = []
        for id in frunze:
            if id == frunzaCurenta.id:
                continue
            lungime = calculLungime(self.coordonate[id][0], self.coordonate[id][1],
                                    self.coordonate[frunzaCurenta.id][0],
                                    self.coordonate[frunzaCurenta.id][1])

            # pentru fiecare frunza pe care inca nu a sarit veirific daca poate sa sara
            if lungime <= frunzaCurenta.greutate_actuala / 3 and not frunzaCurenta.contineInDrum(id):
                # greutatea maxima adimisa de frunza pe care sare si nr de insecte
                # pe care le poseda
                greutate_max_frunza = self.greutati[id]
                nr_insecte_succesor = frunzaCurenta.nr_insecte[id]

                # updatez greutatea in functie de cate insecte poate sa manance
                # avand in vedere ca nu poate depasi greutatea adimisa de frunza

                greutate_noua = frunzaCurenta.greutate_actuala - 1
                nr_insecte_frunza_noua = copy.deepcopy(frunzaCurenta.nr_insecte)
                while greutate_noua <= greutate_max_frunza and nr_insecte_succesor > 0:
                    greutate_noua += 1
                    nr_insecte_succesor -= 1

                nr_insecte_frunza_noua[id] = nr_insecte_succesor

                frunza_noua = Frunza(id, coordonate[id], nr_insecte_frunza_noua, greutate_noua, frunzaCurenta)
                listaSuccesori.append(frunza_noua)
        return listaSuccesori

    def verificaScop(self, frunzaCurenta):
        distanta = calculLungime(0, 0, self.coordonate[frunzaCurenta.id][0], self.coordonate[frunzaCurenta.id][1])
        distantaRamasa = self.raza - distanta

        return distantaRamasa <= frunzaCurenta.greutate_actuala / 3


nrSolutiiCautate = 4

def uniform_cost(gr):
    global nrSolutiiCautate
    global coordonate
    global nr_insecte
    global greutate
    global frunze
    # in coada vom avea doar noduri de tip NodParcurgere (nodurile din arborele de parcurgere)
    c = [Frunza(start, coordonate, nr_insecte, greutate, None)]
    continua = True  # variabila pe care o setez la false cand consider ca s-au afisat suficiente solutii
    while (len(c) > 0 and continua):
        # print("Coada actuala: " + str(c))
        # input()
        nodCurent = c.pop(0)

        if gr.verificaScop(nodCurent):
            nodCurent.afisDrum()
            nrSolutiiCautate -= 1
            if nrSolutiiCautate == 0:
                continua = False
        lSuccesori = gr.genereazaSuccesori(nodCurent)
        for s in lSuccesori:
            i = 0
            for i in range(len(c)):
                if c[i].costNodCurent() >= s.costNodCurent():
                    break
            c.insert(i, s)


def write_in_file(s):
    file = open("output.txt", "a")
    file.write(s)
    file.write("\n")

if __name__ == "__main__":
    raza, greutate, start, frunze, coordonate, nr_insecte, greutati = read_from_file()
    gr = Graph(raza, start, greutate, frunze, coordonate, nr_insecte, greutati)
    uniform_cost(gr)