17561번 - Travel Guide 다국어

Paris counts many hotels. Some are very close to the Orly airport, which is very useful to spend a night before an early flight. Some are very close to the Notre-Dame cathedral which allows tourists to walk around the “Île Saint-Louis” at dawn and enjoy the banks of the Seine. Finally, some are closer to the Disneyland Paris resort which is the most visited tourist attraction. Travelers who come to Paris usually want to stay near these three main Points Of Interest (POIs): Orly, Notre-Dame, and Disneyland.

You are employed by a travel agency and your manager Anna wants to prepare a list of hotels to include in her new travel guide. Her guide contains one entry per station of the metropolitan network. Anna notices that some stations do not have a convenient location with respect to the distance to the three POIs and therefore her guide should not contain a hotel section for such “useless” stations.

Anna considers that a station is useless when another station is closer to all the POIs. Formally a station A is useless when there exists another station B such that B is at least as close to the three POIs as A is and B is strictly closer than A to at least one of those POIs. A station is useful if it is not useless.

Anna asks you how many stations in her guide will have a hotel section. To compute this list you are given the plan of the metropolitan network. The plan of the metropolitan network is an undirected weighted graph. In this graph, each node corresponds to a station (note that each POI is also a station); each edge links two stations and takes a certain time to be traversed in either direction. This graph is connected and the distance between any two stations is the lowest total time of a path between the two nodes.

The input comprises several lines, each consisting of integers separated with single spaces:

• The first line consists of the number N of nodes and the number E of edges.
• Each of the following E lines describes an edge with three integers A, B, and W:
  • A and B are the endpoints of the edge (numbered from 0 to N − 1);
  • W is the weight of the edge.

In the graph:

• Orly corresponds to the station 0;
• Notre-Dame corresponds to the station 1;
• Disneyland corresponds to the station 2.

The output should consist of a single line, whose content is an integer, the number of useful stations.

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