using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 2");
WillReturn.Add("1 20 4 7");
WillReturn.Add("20 2 20 3");
WillReturn.Add("1 3 5");
WillReturn.Add("1 4 6");
//16
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 1");
WillReturn.Add("1 1 1");
WillReturn.Add("10 10 10");
WillReturn.Add("1 2 100");
//3
}
else if (InputPattern == "Input3") {
WillReturn.Add("7 8");
WillReturn.Add("35 29 36 88 58 15 25");
WillReturn.Add("99 7 49 61 67 4 57");
WillReturn.Add("2 3 3");
WillReturn.Add("2 5 36");
WillReturn.Add("2 6 89");
WillReturn.Add("1 6 24");
WillReturn.Add("5 7 55");
WillReturn.Add("1 3 71");
WillReturn.Add("3 4 94");
WillReturn.Add("5 6 21");
//160
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct EdgeInfoDef
{
internal long FromNode;
internal long ToNode;
internal long Cost;
}
static List<EdgeInfoDef> mEdgeInfoList = new List<EdgeInfoDef>();
static long mN;
static long mSuperNodeAir;
static long mSuperNodeSea;
static long[] mXArr;
static long[] mYArr;
static List<string> mInputList;
static void Main()
{
mInputList = GetInputList();
long[] wkArr = mInputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
mN = wkArr[0];
mSuperNodeAir = mN + 1;
mSuperNodeSea = mN + 2;
mXArr = mInputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
mYArr = mInputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
var AnswerKouhoList = new List<long>();
AnswerKouhoList.Add(Kruskal(false, false));
AnswerKouhoList.Add(Kruskal(false, true));
AnswerKouhoList.Add(Kruskal(true, false));
AnswerKouhoList.Add(Kruskal(true, true));
Console.WriteLine(AnswerKouhoList.Min());
}
// 道路の辺を作成
static void AddEdgeRoad()
{
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
foreach (string EachStr in mInputList.Skip(3)) {
SplitAct(EachStr);
long FromNode = wkArr[0];
long ToNode = wkArr[1];
long Cost = wkArr[2];
AddEdge(FromNode, ToNode, Cost);
AddEdge(ToNode, FromNode, Cost);
}
}
// スーパー空港との辺を作成
static void AddEdgeAir()
{
for (long I = 1; I <= mN; I++) {
long FromNode = I;
long ToNode = mSuperNodeAir;
long Cost = mXArr[I - 1];
AddEdge(FromNode, ToNode, Cost);
AddEdge(ToNode, FromNode, Cost);
}
}
// スーパー港との辺を作成
static void AddEdgeSea()
{
for (long I = 1; I <= mN; I++) {
long FromNode = I;
long ToNode = mSuperNodeSea;
long Cost = mYArr[I - 1];
AddEdge(FromNode, ToNode, Cost);
AddEdge(ToNode, FromNode, Cost);
}
}
// 隣接リストに無向辺を追加
static void AddEdge(long pFromNode, long pToNode, long pCost)
{
EdgeInfoDef WillAdd;
WillAdd.FromNode = pFromNode;
WillAdd.ToNode = pToNode;
WillAdd.Cost = pCost;
mEdgeInfoList.Add(WillAdd);
}
// クラスカル法
static long Kruskal(bool pUseAir, bool pUseSea)
{
mEdgeInfoList.Clear();
AddEdgeRoad();
if (pUseAir) AddEdgeAir();
if (pUseSea) AddEdgeSea();
// クラスカル法で解く
var InsUnionFindSizeInfo = new UnionFindSizeInfo();
for (int I = 1; I <= mN + 2; I++) {
InsUnionFindSizeInfo.MakeSet(I);
}
// 枝をコストの昇順にソート
mEdgeInfoList.Sort((a, b) => a.Cost.CompareTo(b.Cost));
long SumCost = 0;
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoList) {
long FromNode = EachEdgeInfo.FromNode;
long ToNode = EachEdgeInfo.ToNode;
long RootNode1 = InsUnionFindSizeInfo.FindSet(EachEdgeInfo.FromNode);
long RootNode2 = InsUnionFindSizeInfo.FindSet(EachEdgeInfo.ToNode);
if (RootNode1 != RootNode2) {
InsUnionFindSizeInfo.Unite(FromNode, ToNode);
SumCost += EachEdgeInfo.Cost;
}
}
// 島の連結判定
long Root1 = InsUnionFindSizeInfo.FindSet(1);
long Root2 = InsUnionFindSizeInfo.FindSet(mSuperNodeAir);
long Root3 = InsUnionFindSizeInfo.FindSet(mSuperNodeSea);
long Size = InsUnionFindSizeInfo.GetSize(1);
if (Root1 == Root2) Size--;
if (Root1 == Root3) Size--;
if (Size == mN) {
return SumCost;
}
return long.MaxValue;
}
}
// UnionFindSizeInfoクラス
internal class UnionFindSizeInfo
{
private class NodeInfoDef
{
internal long ParentNode;
internal long Rank;
internal long Size;
}
private Dictionary<long, NodeInfoDef> mNodeInfoDict =
new Dictionary<long, NodeInfoDef>();
// 要素が1つである木を森に追加
internal void MakeSet(long pNode)
{
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
WillAdd.Size = 1;
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(long pX, long pY)
{
long XNode = FindSet(pX);
long YNode = FindSet(pY);
// 既に同じ木の場合
if (XNode == YNode) return;
long XRank = mNodeInfoDict[XNode].Rank;
long YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
mNodeInfoDict[XNode].Size += mNodeInfoDict[YNode].Size;
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
mNodeInfoDict[YNode].Size += mNodeInfoDict[XNode].Size;
if (XRank == YRank) {
mNodeInfoDict[YNode].Rank++;
}
}
}
// ノードを引数として、木の根を取得
internal long FindSet(long pTargetNode)
{
// 根までの経路上のノードのList
var PathNodeList = new List<long>();
long CurrNode = pTargetNode;
while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
PathNodeList.Add(CurrNode);
CurrNode = mNodeInfoDict[CurrNode].ParentNode;
}
// 経路圧縮 (親ポインタの付け替え)
foreach (long EachPathNode in PathNodeList) {
mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
}
return CurrNode;
}
// ノードを引数として、木のサイズを取得
internal long GetSize(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].Size;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}