Shipping

AtCoder

IDjsc2021_h

Time5000ms

Memory256MB

Difficulty—

In the Republic of AtCoder, there are $N$ cities called City $1$ through City $N$ and $N$ canals called Canal $1$ through Canal $N$. Canal $i$ connects City $i$ and City $A_i$ bidirectionally, and you have to pay the toll of $C_i$ yen to go through it, but after paying the toll once, you can use it any number of times in any direction. It is guaranteed that you can reach from any city to any city using some canals. You are asked to deliver $M$ cargoes in this country. The $i$\-th cargo should be delivered from City $X_i$ to City $Y_i$. There is no way other than using the canals to deliver the cargoes, but you yourself can travel between the cities freely without using the canals. Find the minimum total toll you have to pay to deliver all $M$ cargoes. ## Constraints * $3 \le N \le 2 \times 10^5$ * $1 \le M \le 2 \times 10^5$ * $1 \le A_i \le N$ * $A_i \neq i$ * $1 \le C_i \le 10^9$ * It is possible to reach from any city to any city by using some canals. * $1 \le X_i \le N$ * $1 \le Y_i \le N$ * $X_i \neq Y_i$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $A_1$ $C_1$ $A_2$ $C_2$ $A_3$ $C_3$ $\hspace{13pt} \vdots$ $A_N$ $C_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $X_3$ $Y_3$ $\hspace{13pt} \vdots$ $X_M$ $Y_M$ [samples]

Samples

Input #1

Output #1

10

The figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:  
![image](https://img.atcoder.jp/ghi/00d4990e6b1dd2b0c18ce27618430f91.png)
You can deliver the cargoes as follows to make the total toll $10$ yen:

*   The $1$\-st cargo: use Canal $1, 4$ to deliver it on the route: City $4, 1, 3$.
*   The $2$\-nd cargo: use Canal $3, 1$ to deliver it on this route: City $2, 3, 1$.

Input #2

Output #2

13

Multiple canals may connect the same pair of cities.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Shipping",
    "description": {
      "content": "In the Republic of AtCoder, there are $N$ cities called City $1$ through City $N$ and $N$ canals called Canal $1$ through Canal $N$.   Canal $i$ connects City $i$ and City $A_i$ bidirectionally, and y",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "jsc2021_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the Republic of AtCoder, there are $N$ cities called City $1$ through City $N$ and $N$ canals called Canal $1$ through Canal $N$.  \nCanal $i$ connects City $i$ and City $A_i$ bidirectionally, and y...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments