레이팅 미적용당신은 스마트 자동차를 위한 첨단 중앙집중식 교통 관리 시스템의 설계를 맡았다. 목표는 전역 정보를 이용해, 교외에서 도심으로 차를 몰아야 하는 아침 통근자들에게 교통 체증을 피해 도심에 가장 잘 도착하는 방법을 안내하는 것이다. 안타깝게도 통근자들은 도시를 잘 알고 이기적이기 때문에, 평소보다 오래 걸리는 경로로 가라고 지시할 수는 없다(그러면 안내를 무시할 것이다). 똑같이 빠른 다른 경로로 바꾸도록 설득할 수 있을 뿐이다. 도시의 도로망은 다양한 이동 시간의 양방향 도로로 연결된 교차로들로 이루어져 있다. 각 통근자는 어떤 교차로에서 출발하며, 출발지는 통근자마다 다를 수 있다. 모든 통근자는 같은 곳, 즉 도심인 교차로 1에서 여정을 마친다. 두 통근자(c\(om- mu\)ters)가 같은 도로를 같은 방향으로 동시에 달리기 시작하려 하면 정체가 발생한다. 이를 반드시 피해야 한다. 하지만 두 통근자가 같은 교차로를 동시에 지나가거나, 같은 도로를 서로 다른 시각에 달리기 시작하는 것은 괜찮다. 모든 통근자가 정확히 같은 시각에 여정을 시작하고 누구도 차선책 경로를 택하지 않는다는 조건 아래, 정체 없이 도심까지 운전해 갈 수 있는 통근자의 최대 수를 구하시오. 그림 C.1: 샘플 입력 2의 그림. 그림 C.1에서 자동차들은 원래 위치에 그려져 있다. 한 대는 이미 도심에 있다. 교차로(\(in- te\)rsection) 4에 있는 차들 중 한 대는 교차로 3을 지나는 점선 경로로, 다른 한 대는 교차로 2를 지나는 파선 경로로 갈 수 있다. 하지만 나머지 두 대는 정체를 피하면서 도심에 도달할 수 없다. 따라서 정체 없이 도심에 도달할 수 있는 차는 최대 3대이다.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 세 정수 \(n\), \(m\), \(c\)가 주어진다. \(n\) (\(1 \le n \le 25\,000\))은 교차로의 수, \(m\) (\(0 \le m \le 50\,000\))은 도로의 수, \(c\) (\(0 \le c \le 1\,000\))는 통근자의 수이다. 다음 \(m\)개의 줄에는 각각 도로 하나를 설명하는 세 정수 \(xi\), \(yi\), \(t_{i}\)가 주어진다. \(x_{i}\)와 \(y_{i}\) (\(1 \le x_{i}\), \(y_{i} \le n\))는 도로가 연결하는 서로 다른 교차로이고, \(t_{i}\) (\(1 \le t_{i} \le 10\,000\))는 그 도로를 어느 방향으로든 지나는 데 걸리는 시간이다. 모든 교차로에서 도심에 도달할 수 있다고 가정해도 된다. 마지막 줄에는 통근자들의 출발 교차로를 나열한 \(c\)개의 정수가 주어진다.
정체 없이 도심에 도달할 수 있는 통근자의 최대 수를 출력한다.
3 3 2
1 2 42
2 3 1
2 3 1
2 3
2
4 4 5
1 2 5
1 3 4
4 2 5
4 3 6
4 4 4 4 1
3