CF1027D Mouse Hunt

伯兰州立大学的医学部刚刚结束了招生活动。和以往一样，约80%的申请人都是女生并且她们中的大多数人将在未来4年（真希望如此）住在大学宿舍里。 宿舍楼里有$n$个房间和**一只老鼠**！女孩们决定在一些房间里设置捕鼠器来除掉这只可怕的怪物。在$i$号房间设置陷阱要花费$c_i$伯兰币。房间编号从$1$到$n$。 要知道老鼠不是一直原地不动的，它不停地跑来跑去。如果$t$秒时它在$i$号房间，那么它将在$t+1$秒时跑到$a_i$号房间，但这期间不会跑到别的任何房间里($i=a_i$表示老鼠没有离开原来的房间)。时间从$0$秒开始，一旦老鼠窜到了有捕鼠器的房间里，这只老鼠就会被抓住。 如果女孩们知道老鼠一开始在哪里不就很容易吗？不幸的是，情况不是这样，老鼠在第$0$秒时可能会在从$1$到$n$的任何一个房间内。 那么女孩们最少要花多少钱设置捕鼠器，才能保证老鼠无论从哪个房间开始流窜最终都会被抓到？

无

无

In the first example it is enough to set mouse trap in rooms $ 1 $ and $ 4 $ . If mouse starts in room $ 1 $ then it gets caught immideately. If mouse starts in any other room then it eventually comes to room $ 4 $ . In the second example it is enough to set mouse trap in room $ 2 $ . If mouse starts in room $ 2 $ then it gets caught immideately. If mouse starts in any other room then it runs to room $ 2 $ in second $ 1 $ . Here are the paths of the mouse from different starts from the third example: - $ 1 \rightarrow 2 \rightarrow 2 \rightarrow \dots $ ; - $ 2 \rightarrow 2 \rightarrow \dots $ ; - $ 3 \rightarrow 2 \rightarrow 2 \rightarrow \dots $ ; - $ 4 \rightarrow 3 \rightarrow 2 \rightarrow 2 \rightarrow \dots $ ; - $ 5 \rightarrow 6 \rightarrow 7 \rightarrow 6 \rightarrow \dots $ ; - $ 6 \rightarrow 7 \rightarrow 6 \rightarrow \dots $ ; - $ 7 \rightarrow 6 \rightarrow 7 \rightarrow \dots $ ; So it's enough to set traps in rooms $ 2 $ and $ 6 $ .