sub min{$_[$_[1]<$_[0]]}
for$i(@N=0..-2+map$S[$_]=<>,0..<>){
	for$j(@N){
		$w[$i][$j]=inf;
	}
}
/ .* /,$w[$`][$&]=$w[$&][$`]=$' for<>;
for$m(@N){
	for$i(@N){
		for$j(@N){
			$w[$i][$j]=min(
				$w[$i][$j],
				$w[$i][$m]+$w[$m][$j]
			)
		}
	}
}
$\=inf;
for$x(@@=1..@S-3){
	for$y(@@){
		if($x-$y){
			$\=min(
				$\,
				$S[$x]+$S[$y]+$w[0][$x]+$w[$x][$y]+$w[$y][@S-2]
			)
		}
	}
}
print