Aniuta and Google
Tenth-grader Anya is passionate about microbiology and is preparing a report on new types of viruses. As is well known, Google is a great resource, so Anya frequently uses it. While preparing her report, she extensively used the search engine and gathered valuable information. Here’s how Anya worked:
She started by entering a search query into Google and received several links that caught her interest.
Anya understood that if she loaded a page from her list, it might contain links to other pages, which she could also load. She followed this process, loading all the pages that intrigued her.
She continued this process until her list contained exactly n different pages.
However, just as her report was nearly complete, Murzik, Anya's beloved cat, chewed through the wire again, cutting off the Internet! This meant the last necessary page wasn't downloaded. Unfortunately, Anya had recorded all the pages in her list by numbers 1, 2, ..., n, but hadn't noted their full web addresses. Now, Anya needs to find and download this last page.
Murzik, the culprit, was confined to the kitchen, much to his dismay. The wire was replaced, and Anya is now ready to search Google again to find the last page in her list of sources—the one Murzik prevented her from accessing. Anya has a list of pages, and for each page, she knows:
the size of the page in bytes,
a list of pages accessible from that page.
Anya is eager to know the minimum amount of data she needs to download to follow the links to the required page. Help her solve this problem!
Input
The first line contains the number of Internet pages n in the list. The following n lines describe each page: the i-th line contains an integer p[i]—the size of the page in bytes, and m[i]—the number of pages accessible from the i-th page. Following this, the line lists m[i] integers, which are the numbers of the pages accessible from the i-th page. The first page in this list is Google, and the last page is the one Anya needs to find a path to. Pages are numbered starting from 1. The value n does not exceed 100. The size of each page is non-zero and does not exceed 1 megabyte, specified in bytes.
Output
Output a single number—the minimum number of bytes that need to be downloaded to follow the links from the first page to the last. It is guaranteed that such a path always exists.