D. Highway
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the Lead Engineer for the province of Spongeland, which consists of $$$n$$$ cities. Your mission is to establish a highway network such that every city is reachable from every other city through a series of connected roads.

There are $$$m$$$ potential highway proposals available for construction. Each proposal $$$i$$$ (where $$$1 \le i \le m$$$) is defined by:

  • Two cities $$$(u_i, v_i)$$$ to be connected.
  • A construction cost $$$c_i$$$.

However, the provincial government has already signed a non-negotiable contract for proposal $$$j$$$. This specific highway must be included in your final network, regardless of its cost or how it affects the overall efficiency.

Calculate the minimum total cost to connect all $$$n$$$ cities, ensuring that proposal $$$j$$$ is part of the infrastructure.

Input

The first line contains two integers: $$$n$$$ (number of cities) and $$$m$$$ (number of proposals). The second line contains an integer $$$j$$$, representing the index of the mandatory proposal. The following $$$m$$$ lines each contain three integers $$$u_i, v_i$$$, and $$$c_i$$$, representing the $$$i$$$-th proposal.

  • $$$2 \le n \le 10^5$$$
  • $$$1 \le j \le m$$$
  • $$$n - 1 \le m \le 2 \times 10^5$$$
  • $$$1 \le u_i, v_i \le n$$$ and $$$u_i \neq v_i$$$
  • $$$1 \le c_i \le 10^9$$$
  • Uniqueness: No two proposals connect the same pair of cities.
  • Connectivity: The set of $$$m$$$ proposals is guaranteed to form a connected graph.
Output

A single integer representing the minimum cost to connect all $$$n$$$ cities including proposal $$$j$$$. Note: Use a 64-bit integer type to avoid overflow.

Example
Input
4 5
3
1 2 10
2 3 5
3 4 50
1 4 20
2 4 15
Output
65
Note

The mandatory proposal is proposal $$$3$$$, which connects cities $$$3$$$ and $$$4$$$ with cost $$$50$$$.

After including this proposal, one optimal way to finish connecting all cities is to also include: $$$$$$ (2, 3) \text{ with cost } 5 $$$$$$ and $$$$$$ (1, 2) \text{ with cost } 10. $$$$$$

These three highways connect all $$$4$$$ cities: $$$$$$ 1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4. $$$$$$

The total cost is $$$$$$ 50 + 5 + 10 = 65. $$$$$$

Therefore, the minimum total cost including proposal $$$3$$$ is $$$65$$$.