L'archipel JOI est un petit État insulaire situé dans l'océan Pacifique. Il compte $N$ îles, numérotées de $1$ à $N$.

Les communications entre les îles de l'archipel JOI s'effectuent principalement par radio. Chaque île possède un émetteur et un récepteur. L'émetteur peut envoyer des ondes dans toutes les directions, mais le récepteur ne peut recevoir que les ondes provenant d'une direction précise. Ainsi, chaque récepteur ne peut recevoir que les ondes d'une seule île déterminée. Toutefois, en changeant son orientation, on peut changer l'île dont il reçoit les ondes.

Actuellement, le récepteur de l'île $i$ ($1 \le i \le N$) peut recevoir les ondes de l'île $A_i$ ($A_i\ne i$). Le coût du changement d'orientation du récepteur de l'île $i$ est $C_i$, quelle que soit la nouvelle orientation.

L'archipel JOI propose un service public de télégrammes. Lorsque le récepteur de l'île $j$ ($1 \le j \le N$, $j\ne i$) peut recevoir les ondes de l'île $i$ ($1 \le i \le N$), on peut envoyer un télégramme de l'île $i$ à l'île $j$ par radio. Les télégrammes peuvent également transiter par plusieurs îles. Autrement dit, pour trois îles $i,j,k$ ($1 \le i,j,k \le N$, toutes distinctes), si l'on peut envoyer un télégramme de $i$ à $j$ et de $j$ à $k$, on peut en envoyer un de $i$ à $k$. Aucun autre moyen que la radio ne permet d'envoyer des télégrammes.

Vous êtes le ministre des Communications de l'archipel JOI et souhaitez qu'il soit possible d'envoyer un télégramme de n'importe quelle île à n'importe quelle autre. Pour cela, il peut être nécessaire de changer l'orientation des récepteurs de certaines îles. Le coût de ces changements est la somme des coûts de changement d'orientation de chacun de ces récepteurs.

Calculez le coût minimal permettant d'envoyer des télégrammes de n'importe quelle île à n'importe quelle autre.

Tâche

Étant donnés le nombre d'îles de l'archipel JOI et les informations sur leurs récepteurs, écrivez un programme qui détermine le coût minimal permettant d'envoyer un télégramme de n'importe quelle île à n'importe quelle autre.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient un entier $N$, indiquant que l'archipel JOI compte $N$ îles.
• La $i$-ème ligne ($1 \le i \le N$) parmi les $N$ lignes suivantes contient deux entiers $A_i,C_i$ séparés par un espace. Le récepteur de l'île $i$ peut actuellement recevoir les ondes de l'île $A_i$, et le coût du changement de son orientation est $C_i$.

Sortie

Écrivez sur une ligne de la sortie standard le coût minimal permettant d'envoyer un télégramme de n'importe quelle île à n'importe quelle autre.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $2 \le N \le 100\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $A_i \ne i$ ($1 \le i \le N$).
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Sous-tâches

Sous-tâche 1 [10 points]

• $N \le 10$.

Sous-tâche 2 [30 points]

• $N \le 15$.

Sous-tâche 3 [30 points]

• $N \le 3\,000$.

Sous-tâche 4 [30 points]

Il n'y a pas de contrainte supplémentaire.

Exemples

Entrée 1

4
2 2
1 4
1 3
3 1

Sortie 1

4

Remarque

Changeons l'orientation du récepteur de l'île $2$ pour qu'il reçoive les ondes de l'île $4$. Il devient alors possible d'envoyer un télégramme de n'importe quelle île à n'importe quelle autre, pour un coût de $4$.

Aucun changement d'orientation des récepteurs ne permet un coût inférieur à $4$, donc on affiche 4.

Entrée 2

4
2 2
1 6
1 3
3 1

Sortie 2

5

Remarque

Changeons d'abord l'orientation du récepteur de l'île $1$ pour qu'il reçoive les ondes de l'île $4$. Changeons ensuite celle du récepteur de l'île $3$ pour qu'il reçoive les ondes de l'île $2$. Il devient alors possible d'envoyer un télégramme de n'importe quelle île à n'importe quelle autre, pour un coût de $2+3=5$.

Aucun changement d'orientation des récepteurs ne permet un coût inférieur à $5$, donc on affiche 5.

Entrée 3

4
2 2
1 3
4 2
3 3

Sortie 3

4

Remarque

Il suffit de changer l'orientation des récepteurs des îles $1$ et $3$.

Entrée 4

3
2 1
3 1
1 1

Sortie 4

0

Remarque

Il n'est nécessaire de changer l'orientation du récepteur d'aucune île.