JOI 诸岛是漂浮在太平洋上的一个小型群岛国家。JOI 诸岛共有 个岛屿,编号从 1 到 。
在 JOI 诸岛,岛屿之间的通信主要依靠无线电波进行。每个岛屿都配备了一台发射机和一台接收机。发射机可以向所有方向发送无线电波,但接收机只能接收来自特定方向的无线电波。因此,通过调整接收机的方向,可以改变它能接收来自哪个岛屿的无线电波。
目前,岛屿 ()的接收机能够接收来自岛屿 ()的无线电波。此外,调整岛屿 的接收机方向所需的成本为 ,与调整后的方向无关。
JOI 诸岛正在开展一项公共服务——电报服务。当岛屿 ()的无线电波能够被岛屿 ()的接收机接收时,岛屿 可以通过无线电通信向岛屿 发送电报。此外,电报可以通过若干岛屿中转发送。也就是说,当岛屿 、岛屿 、岛屿 (,且 互不相同)之间满足:岛屿 可向岛屿 发送电报,岛屿 可向岛屿 发送电报时,岛屿 也可向岛屿 发送电报。不允许使用无线电通信以外的方式发送电报。
作为 JOI 诸岛的通信大臣,你希望实现从任意岛屿向任意其他岛屿发送电报的目标。为此,可能需要调整若干岛屿接收机的方向。调整若干岛屿接收机方向所需的总成本,是各岛屿调整接收机方向所需成本的总和。
请计算为了实现从任意岛屿向任意其他岛屿发送电报的目标所需的最小成本。
题目
给定 JOI 诸岛的岛屿数量,以及每个岛屿接收机的相关信息,编写程序求出为了实现从任意岛屿向任意其他岛屿发送电报的目标所需的最小成本。