{"raw_statement":[{"iden":"statement","content":"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.\n\nAnna 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.\n\nAnna 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.\n\nThe input comprises several lines, each consisting of integers separated with single spaces:\n\nIn the graph: \n\n*Limits* \n\nThe output should consist of a single line, whose content is an integer, the number of useful stations.\n\n*Explanation of Sample 1:* \n\n*Explanation of Sample 2:*\n\nIn this graph (depicted on the bottom), three stations are useful: _Orly_, _Disneyland_, and _Notre-Dame_. The stations corresponding to _Orly_, _Disneyland_, _Notre-Dame_ are the closest stations to themselves. All stations have a POI at distance 2 except for _Gare du Nord_, which is at distance 1 to all POIs, and Orly which is at distance 1 to all POIs but at a distance of 0 to itself. Therefore _Gare du Nord_ is useless. \n\n"},{"iden":"input","content":"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. *Limits*   $4 <= N <= 100000$;  $E <= 500000$;  $1 <= w <= 100$. "},{"iden":"output","content":"The output should consist of a single line, whose content is an integer, the number of useful stations."},{"iden":"examples","content":"Input5 4\n0 3 1\n1 3 1\n2 3 1\n4 3 1\nOutput4\nInput5 6\n0 3 1\n1 3 1\n2 3 1\n4 3 1\n0 1 1\n0 2 1\nOutput3\n"},{"iden":"note","content":"*Explanation of Sample 1:*    This graph is depicted on the top with _Gare du Nord_ as node 3 and _La Défense_ as node 4. In this graph, four stations are useful: _Orly_, _Disneyland_, _Notre-Dame_, and _Gare du Nord_. The stations corresponding to _Orly_, _Disneyland_, _Notre-Dame_ are the closest stations to themselves. All stations have a POI at distance 2 except for _Gare du Nord_, which is at distance 1 to all POIs. Finally, _La Défense_ is useless because it is at distance 2 from all POIs. For instance, _Orly_ is as close as _La Défense_ to _Notre-Dame_ and _Disneyland_ but strictly closer to _Orly_ and thus _Orly_ witnesses that the station _La Défense_ is useless.*Explanation of Sample 2:*In this graph (depicted on the bottom), three stations are useful: _Orly_, _Disneyland_, and _Notre-Dame_. The stations corresponding to _Orly_, _Disneyland_, _Notre-Dame_ are the closest stations to themselves. All stations have a POI at distance 2 except for _Gare du Nord_, which is at distance 1 to all POIs, and Orly which is at distance 1 to all POIs but at a distance of 0 to itself. Therefore _Gare du Nord_ is useless.   "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected weighted connected graph, where:  \n- $ V $ is the set of stations (nodes),  \n- $ E $ is the set of edges with positive integer weights representing traversal times.  \n\nLet $ P \\subseteq V $ be the set of three Points of Interest (POIs).  \n\nFor any station $ v \\in V $, define the distance vector:  \n$$\nd(v) = \\left( d(v, p_1), d(v, p_2), d(v, p_3) \\right) \\in \\mathbb{R}_{\\geq 0}^3\n$$  \nwhere $ d(v, p_i) $ is the shortest path distance from $ v $ to POI $ p_i \\in P $.\n\n**Constraints**  \n- $ |V| \\geq 3 $, $ |P| = 3 $,  \n- $ G $ is connected,  \n- All edge weights are positive integers.\n\n**Objective**  \nA station $ v \\in V $ is **useless** if there exists another station $ u \\in V \\setminus \\{v\\} $ such that:  \n$$\nd(u) \\leq d(v) \\quad \\text{and} \\quad d(u) \\neq d(v)\n$$  \n(i.e., $ d(u)_i \\leq d(v)_i $ for all $ i \\in \\{1,2,3\\} $, and $ d(u)_j < d(v)_j $ for at least one $ j $).\n\nA station is **useful** if it is not useless.\n\nCompute the number of useful stations in $ V $.","simple_statement":"Given a weighted undirected graph where each node is a station and three special stations are POIs, find how many stations are \"useful\". A station is useless if there exists another station that is at least as close to all three POIs and strictly closer to at least one POI. Otherwise, it’s useful. Count the useful stations.","has_page_source":false}