아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Игра

시간 제한2초메모리 제한1024 MB

요약
간선이 마을들로 세분된 그래프에서 두 말이 움직이되 한 도로에는 한 명만 있을 수 있고, 먼저 수도에 도착하는 사람을 가린다.
난이도

보통10점 중 7점

유형
그래프, BFS, 게임 이론, 최단 경로
정답자
아직 제출이 없습니다

문제

Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут иметь различную длину. При этом, если длина дороги между двумя городами равна xx, то на этой дороге в ряд находятся (x−1)(x - 1) деревень, можно перейти от города к крайней деревне на дороге, от этой деревне к соседней, и т. д.

У каждого их игроков есть по фишке, исходно фишки игроков расположены в некоторых различных городах. Игроки ходят по очереди: за один ход можно передвинуть фишку в город или деревню, которые соединены с текущей вершиной напрямую, либо можно оставить фишку на месте. Начинает первый игрок.

Однако есть одно ограничение: если один из игроков находится в одной из деревень на дороге между двумя городами, то другой не может переходить ни в одну деревню, находящуюся на этой дороге.

Цель каждого из игроков заключается в том, чтобы добраться в столицу первым.

입력

В первой строке входного файла находятся два числа nn --- число городов и mm --- число дорог (1≤n,m≤1051 \le n,m \le 10^5).

В следующих mm строках находятся по три числа aa, bb и cc, означающих, что между городами aa и bb есть дорога длиной cc, содержащая c−1c - 1 деревню (a≠ba \neq b, 1≤c≤1091 \le c \le 10^9).

В последней строке находится три числа s_1s\_1, s_2s\_2 --- номера городов в которых изначально находятся фишки игроков (s_1≠s_2s\_1 \neq s\_2), и tt --- номер города, являющегося столицей.

Гарантируется, что по дорогам из любого города можно добраться в любой другой.

출력

В выходной файл выведите <<First>>, если первым в столицу доберется первый игрок, и <<Second>>, если второй.

예제1

  1. 예제 1

    입력
    4 3
    1 3 2
    3 2 3
    4 3 1
    1 4 2
    
    예상 출력
    Second