여행 안내서

파리에는 호텔이 많다. 오를리 공항과 아주 가까운 호텔도 있어서 이른 비행기 편을 타기 전에 하룻밤 묵기에 좋다. 노트르담 대성당과 아주 가까운 호텔도 있어서 관광객이 새벽에 생루이섬을 걸으며 센강 강변을 즐길 수 있다. 디즈니랜드 파리 리조트와 가까운 호텔도 있는데, 이곳은 방문객이 가장 많은 관광지이다. 파리에 오는 여행자는 보통 이 세 주요 관심 지점(POI), 즉 오를리, 노트르담, 디즈니랜드 근처에 묵기를 원한다.

당신은 여행사에 다니고, 상사 안나는 새 여행 안내서에 넣을 호텔 목록을 준비하려 한다. 안내서에는 지하철망의 역마다 항목이 하나씩 들어간다. 안나는 일부 역이 세 POI까지의 거리라는 관점에서 위치가 좋지 않아, 그런 "쓸모없는" 역에는 호텔 항목을 넣지 않아야 한다는 점을 알아차린다.

안나는 다른 역이 모든 POI에 더 가까우면 그 역이 쓸모없다고 본다. 형식적으로 역 A가 쓸모없다는 것은, 다른 역 B가 존재하여 B가 세 POI 모두에 대해 A만큼 가깝거나 더 가깝고, 그 POI 중 적어도 하나에 대해서는 B가 A보다 더 가까운 경우를 말한다. 쓸모없지 않은 역은 유용한 역이다.

안나는 안내서에서 호텔 항목이 들어갈 역이 몇 개인지 묻는다. 이 목록을 계산하기 위해 지하철망의 노선도가 주어진다. 지하철망 노선도는 가중치가 있는 무방향 그래프이다. 이 그래프에서 각 정점은 역에 대응한다(POI도 역이라는 점에 유의한다). 각 간선은 두 역을 잇고, 어느 방향으로든 지나는 데 일정한 시간이 걸린다. 이 그래프는 연결되어 있고, 두 역 사이의 거리는 두 정점 사이의 경로 중 총 시간이 가장 짧은 경로의 총 시간이다.

입력은 여러 줄로 이루어지고, 각 줄에는 정수가 하나의 공백으로 구분되어 들어간다.

• 첫째 줄에는 정점의 수 N과 간선의 수 E가 들어간다.

• 다음 E개 줄은 각각 간선 하나를 세 정수 A, B, W로 나타낸다.

  • A와 B는 간선의 양 끝점이다(0부터 N − 1까지 번호가 매겨진다).
  • W는 간선의 가중치이다.

그래프에서:

• 오를리는 역 0에 대응한다.
• 노트르담은 역 1에 대응한다.
• 디즈니랜드는 역 2에 대응한다.

출력은 한 줄이고, 그 내용은 정수 하나, 즉 유용한 역의 수이다.

• 4 ≤ N ≤ 100 000;
• E ≤ 500 000;
• 1 ≤ w ≤ 100.