{"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 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.  \nIt is guaranteed that you can reach from any city to any city using some canals.\nYou are asked to deliver $M$ cargoes in this country. The $i$\\-th cargo should be delivered from City $X_i$ to City $Y_i$.  \nThere 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.\nFind the minimum total toll you have to pay to deliver all $M$ cargoes.\n\n## Constraints\n\n*   $3 \\le N \\le 2 \\times 10^5$\n*   $1 \\le M \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le N$\n*   $A_i \\neq i$\n*   $1 \\le C_i \\le 10^9$\n*   It is possible to reach from any city to any city by using some canals.\n*   $1 \\le X_i \\le N$\n*   $1 \\le Y_i \\le N$\n*   $X_i \\neq Y_i$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $C_1$\n$A_2$ $C_2$\n$A_3$ $C_3$\n$\\hspace{13pt} \\vdots$\n$A_N$ $C_N$\n$X_1$ $Y_1$\n$X_2$ $Y_2$\n$X_3$ $Y_3$\n$\\hspace{13pt} \\vdots$\n$X_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"jsc2021_h","tags":[],"sample_group":[["4 2\n3 3\n1 7\n2 5\n1 2\n4 3\n2 1","10\n\nThe figure below shows the cities and canals in this country, where numbers along the lines representing canals represent the tolls:  \n![image](https://img.atcoder.jp/ghi/00d4990e6b1dd2b0c18ce27618430f91.png)\nYou can deliver the cargoes as follows to make the total toll $10$ yen:\n\n*   The $1$\\-st cargo: use Canal $1, 4$ to deliver it on the route: City $4, 1, 3$.\n*   The $2$\\-nd cargo: use Canal $3, 1$ to deliver it on this route: City $2, 3, 1$."],["5 2\n2 2\n5 5\n5 7\n2 4\n3 10\n3 5\n4 1","13\n\nMultiple canals may connect the same pair of cities."],["11 4\n8 1\n9 9\n8 10\n8 3\n1 2\n11 3\n9 2\n6 5\n3 4\n1 7\n3 2\n7 8\n10 1\n4 9\n11 6","26"]],"created_at":"2026-03-03 11:01:14"}}