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