P10617 [ICPC 2013 WF] Surely You Congest

你负责设计一个先进的集中交通管理系统，以便为智能汽车提供服务。目标是利用全局信息指导早晨从郊区驾车前往市中心的通勤者，帮助他们避免交通拥堵。 不幸的是，由于通勤者了解城市且自私，你不能简单地让他们走比平时更慢的路线（否则他们会忽略你的指示）。你只能说服他们改变到同样快的不同路线。 城市的道路网络由连接双向道路的交叉口组成，各条道路的行驶时间不同。每个通勤者从某个交叉口出发，这些交叉口因人而异。所有通勤者的行程终点都是市中心的 1 号交叉口。如果两名通勤者同时在同一方向上行驶在同一条道路上，会造成拥堵；你必须避免这种情况。然而，如果两名通勤者同时经过同一个交叉口或者在不同时间使用同一条道路，这是允许的。 确定在所有通勤者同时开始旅程且没有任何人走次优路线的情况下，最多有多少通勤者可以在不拥堵的情况下开车到市中心。 

输入由一个单独的测试用例组成。第一行包含三个整数 $n, m, c$，其中 $n (1 \leq n \leq 25 000)$ 表示交叉口的数量，$m (0 \leq m \leq 50 000)$ 表示道路的数量，$c (0 \leq c \leq 1 000)$ 表示通勤者的数量。接下来的 $m$ 行中的每一行包含三个整数 $x_i, y_i, t_i$，描述了一条道路，其中 $x_i$ 和 $y_i (1 \leq x_i, y_i \leq n)$ 是道路连接的不同交叉口，$t_i (1 \leq t_i \leq 10 000)$ 是沿该道路行驶的时间。最后一行包含 $c$ 个整数，列出了通勤者的起始交叉口。

显示最多有多少通勤者可以在不拥堵的情况下到达市中心。 翻译来自于：[ChatGPT](https://chatgpt.com/)。