In a distant world, there are two countries: the Kingdom of Jason, located at the western end of the continent, and the Kingdom of Chris, located at the eastern end. The people of the two countries worship two opposing gods: the Kingdom of Jason worships the god of darkness and destruction, Zeng-Blazer, while the Kingdom of Chris worships the god of light and eternity, Spring-Blazer.

In January of the year 8012 of the Fantasy Calendar, the Kingdom of Jason officially declared Zeng-Blazer as their only god and began persecuting the followers of Spring-Blazer within their borders.

On March 2, 8012, the followers of Spring-Blazer in the town of Oracle, located in the eastern part of the Kingdom of Jason, launched an uprising.

On March 7, 8012, the uprising in Oracle was brutally suppressed by the army of the Kingdom of Jason.

On March 8, 8012, the Kingdom of Chris declared war on the Kingdom of Jason. The Chris Legion, consisting of hundreds of thousands of troops, arrived at the border and stood in a standoff against the Jason Legion.

In April 8012, the Chris Legion broke through the Jason Legion's defense line and entered Oracle, liberating the surviving followers of Spring-Blazer.

The war then entered a stalemate, dragging on for a long time. The fighting was fierce, with gunfire and smoke filling the air, leaving the people in misery.

Late at night on May 12, 8012, Spring-Blazer delivered an oracle: "Trust me, earn eternal life." The morale of the Chris Legion soared. As the commander of the Chris Legion, you decide to take this opportunity to launch a surprise attack and defeat the Kingdom of Jason in one fell swoop. Specifically, the Kingdom of Jason has $N$ cities connected by $M$ one-way roads. Oracle is city $1$, and the capital of the Kingdom of Jason is city $N$. You only need to destroy the Great Temple of Zeng-Blazer located in the capital of the Kingdom of Jason, and the faith, army, and everything else of the Kingdom of Jason will collapse and vanish.

To minimize your own losses, you decide to use suicide robots to complete this mission. The only difficulty is that some cities in the Kingdom of Jason are protected by barriers, and you cannot enter a city without destroying its barrier. Each city's barrier is maintained by several barrier generators distributed in other cities. If you want to enter a city, you must destroy all the barrier generators that maintain that city's barrier.

You now have an infinite number of suicide robots. Once a robot enters a city, it can detonate instantly to destroy a target (a barrier generator or the Great Temple of the Kingdom of Jason), and the robot itself will also be destroyed. You need to find the minimum time required to destroy the Kingdom of Jason.

Input

The first line of the input contains two positive integers $N$ and $M$.

The next $M$ lines each contain three positive integers $u_i, v_i, w_i$, representing a one-way road from city $u_i$ to city $v_i$, which takes $w_i$ time for a suicide robot to traverse.

Following this are $N$ lines, each describing a city. Each line starts with a positive integer $l_i$, the number of barrier generators used to maintain the barrier of that city. This is followed by $l_i$ city indices between $1$ and $N$, representing the location of each barrier generator. If $l_i = 0$, it means the city is not protected by a barrier. It is guaranteed that $l_1 = 0$.

Output

The output contains a single positive integer, the minimum time required to defeat the Kingdom of Jason.

Examples

Input 1

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

Output 1

5

Constraints

For 20% of the data, $N \le 15, M \le 50$; For 50% of the data, $N \le 500, M \le 6,000$; For 100% of the data, $N \le 3,000, M \le 70,000, 1 \le w_i \le 10^8$.

The input data is guaranteed to have a solution, and no barrier generator maintaining a city's barrier will be located inside that city.

There may be more than one road connecting two cities, and there may be roads from a city to itself.

Figure 1. Initial state of the city network