sub min{$_[$_[1]<$_[0]]}
$S[$_]=<>for 0..<>-1;
for$i(@N=0..$#S){
	for$j(@N){
		$w[$i][$j]=inf;
	}
#	$w[$i][$i]=0;
}
<>;
/ .* /,$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-2){
	for$y(@@){
		if($x-$y){
			$\=min(
				$\,
				$S[$x]+$S[$y]+$w[0][$x]+$w[$x][$y]+$w[$y][$#S]
			)
		}
	}
}
print