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("3 1");
WillReturn.Add("0 0 1");
WillReturn.Add("0 1 1");
WillReturn.Add("1 0 1");
WillReturn.Add("1 1 1");
//2.000000000000
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 1");
WillReturn.Add("0 10 1");
WillReturn.Add("10 0 2");
WillReturn.Add("10 20 3");
WillReturn.Add("10 10 1");
//210.000000000000
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
// 塔の入力情報
struct TowerInfoDef
{
internal bool IsBig;
internal int X;
internal int Y;
internal int C;
}
static List<TowerInfoDef> mTowerInfoList = new List<TowerInfoDef>();
// 小さい塔の添字のList
static List<int> mSmallTowerIndList = new List<int>();
// 無向グラフの辺の情報
struct EdgeInfoDef
{
internal int FromNode;
internal int ToNode;
internal double Cost;
}
static List<EdgeInfoDef> mEdgeInfoList = new List<EdgeInfoDef>();
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int N = wkArr[0];
int M = wkArr[1];
foreach (string EachStr in InputList.Skip(1).Take(N)) {
SplitAct(EachStr);
TowerInfoDef WillAdd;
WillAdd.IsBig = true;
WillAdd.X = wkArr[0];
WillAdd.Y = wkArr[1];
WillAdd.C = wkArr[2];
mTowerInfoList.Add(WillAdd);
}
foreach (string EachStr in InputList.Skip(1 + N)) {
SplitAct(EachStr);
TowerInfoDef WillAdd;
WillAdd.IsBig = false;
WillAdd.X = wkArr[0];
WillAdd.Y = wkArr[1];
WillAdd.C = wkArr[2];
mTowerInfoList.Add(WillAdd);
}
// 小さい塔の添字のList
for (int I = 0; I <= mTowerInfoList.Count - 1; I++) {
if (mTowerInfoList[I].IsBig == false) {
mSmallTowerIndList.Add(I);
}
}
List<HashSet<int>> NonUseSmallTowerSetList = DeriveNonUseSmallTowerSetList();
for (int I = 0; I <= mTowerInfoList.Count - 1; I++) {
for (int J = I + 1; J <= mTowerInfoList.Count - 1; J++) {
EdgeInfoDef WillAdd;
WillAdd.FromNode = I;
WillAdd.ToNode = J;
double XDiff = mTowerInfoList[I].X - mTowerInfoList[J].X;
double YDiff = mTowerInfoList[I].Y - mTowerInfoList[J].Y;
double Cost = Math.Sqrt(XDiff * XDiff + YDiff * YDiff);
// 色が違う場合は、コストを10倍にする
if (mTowerInfoList[I].C != mTowerInfoList[J].C) {
Cost *= 10D;
}
WillAdd.Cost = Cost;
mEdgeInfoList.Add(WillAdd);
}
}
// 枝をコストの昇順にソート
mEdgeInfoList.Sort((a, b) => a.Cost.CompareTo(b.Cost));
double Answer = double.MaxValue;
foreach (HashSet<int> EachNonUseSmallTowerSet in NonUseSmallTowerSetList) {
double AnswerKouho = DeriveMST(EachNonUseSmallTowerSet);
Answer = Math.Min(Answer, AnswerKouho);
}
Console.WriteLine(Answer);
}
// 使用する小さな塔のIndSetを引数として、MSTのコストを返す
static double DeriveMST(HashSet<int> pNonUseSmallTowerSet)
{
// クラスカル法で解く
var InsUnionFind = new UnionFind();
for (int I = 0; I <= mTowerInfoList.Count - 1; I++) {
if (pNonUseSmallTowerSet.Contains(I)) continue;
InsUnionFind.MakeSet(I);
}
double SumCost = 0;
foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoList) {
if (pNonUseSmallTowerSet.Contains(EachEdgeInfo.FromNode)) continue;
if (pNonUseSmallTowerSet.Contains(EachEdgeInfo.ToNode)) continue;
int FromNode = EachEdgeInfo.FromNode;
int ToNode = EachEdgeInfo.ToNode;
int RootNode1 = InsUnionFind.FindSet(EachEdgeInfo.FromNode);
int RootNode2 = InsUnionFind.FindSet(EachEdgeInfo.ToNode);
if (RootNode1 != RootNode2) {
InsUnionFind.Unite(FromNode, ToNode);
SumCost += EachEdgeInfo.Cost;
}
}
return SumCost;
}
struct JyoutaiDef
{
internal int CurrInd;
internal HashSet<int> SmallTowerSet;
}
//DFSで、未使用の小さい塔の候補を列挙
static List<HashSet<int>> DeriveNonUseSmallTowerSetList()
{
var NonUseSmallTowerSetList = new List<HashSet<int>>();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrInd = 0;
WillPush.SmallTowerSet = new HashSet<int>();
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
NonUseSmallTowerSetList.Add(Popped.SmallTowerSet);
for (int I = Popped.CurrInd; I <= mSmallTowerIndList.Count - 1; I++) {
WillPush.CurrInd = I + 1;
WillPush.SmallTowerSet = new HashSet<int>(Popped.SmallTowerSet);
WillPush.SmallTowerSet.Add(mSmallTowerIndList[I]);
Stk.Push(WillPush);
}
}
return NonUseSmallTowerSetList;
}
}
// UnionFindクラス
internal class UnionFind
{
private class NodeInfoDef
{
internal int ParentNode;
internal int Rank;
}
private Dictionary<int, NodeInfoDef> mNodeInfoDict =
new Dictionary<int, NodeInfoDef>();
// 要素が1つである木を森に追加
internal void MakeSet(int pNode)
{
NodeInfoDef WillAdd = new NodeInfoDef();
WillAdd.ParentNode = pNode;
WillAdd.Rank = 0;
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(int pX, int pY)
{
int XNode = FindSet(pX);
int YNode = FindSet(pY);
int XRank = mNodeInfoDict[XNode].Rank;
int YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
if (XRank == YRank) {
mNodeInfoDict[YNode].Rank++;
}
}
}
// ノードを引数として、木の根を取得
internal int FindSet(int pTargetNode)
{
// 根までの経路上のノードのList
var PathNodeList = new List<int>();
int CurrNode = pTargetNode;
while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
PathNodeList.Add(CurrNode);
CurrNode = mNodeInfoDict[CurrNode].ParentNode;
}
// 経路圧縮 (親ポインタの付け替え)
foreach (int EachPathNode in PathNodeList) {
NodeInfoDef wkNodeInfo = mNodeInfoDict[EachPathNode];
wkNodeInfo.ParentNode = CurrNode;
mNodeInfoDict[EachPathNode] = wkNodeInfo;
}
return CurrNode;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}