8182: 无向带权图--最近的村庄
[Creator : ]
Description
某地有许多村庄，一些村庄间有道路连接。
请问从某个村庄出发通过村庄间的道路可以到达的最近的村庄。
请问从某个村庄出发通过村庄间的道路可以到达的最近的村庄。
Input
第一行：n m。n表示村庄数量，m表示道路数量
以下m行，每行为：f t w。表示村庄f到村庄t有长为w的道路。
接下来一行：q，表示询问的村庄。
以下m行，每行为：f t w。表示村庄f到村庄t有长为w的道路。
接下来一行：q，表示询问的村庄。
Output
从村庄q出发通过道路可以到达的最近的村庄的编号。
Constraints
$1 \leq n \leq 100$
$1 \leq q \leq n$
$1 \leq m \leq 2,000$
$1 \leq w \leq 1,000$
$1 \leq q \leq n$
$1 \leq m \leq 2,000$
$1 \leq w \leq 1,000$
Sample 1 Input
3 3
1 2 1
2 3 2
3 1 3
1
Sample 1 Output
2