三大战役的平津战场上，傅作义集团在以北平、天津为中心，东起唐山西至张家口的铁路线上摆起了一字长蛇阵，并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走，指挥官制定了先切断敌人东西两头退路然后再逐个歼灭敌人的战略方针。秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面。
现在有 N 个城市（编号为1~N，其中 K 个被敌方军团占领了，N 个城市间有 N-1 条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你 K 个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这 K 个地方军团互相隔离开，以便第二步逐个击破敌人。