!>
!! @brief Floyd-Warshallのアルゴリズムを扱います
!! @date  2016/05/07
!!



!!**********************************************************************
!! Floyd-Warshallモジュール(モジュールにする必要はないのかもしれないが。。)
!!**********************************************************************

module module_floyd_warshall
  implicit none

  public  :: floyd_warshall
  integer, parameter, public :: inf = 12345678
  
contains

  !>
  !! @brief   全点対最短経路問題をFloyd-Warshallのアルゴリズムで解きます
  !! @param[in] integer W(:,:)  隣接行列W(ただしW(i,i) = 0であり、i~p~>jを満たす道pが存在しなければW(i,j)=inf)
  !! @return  最短路重みの格納した行列D  
  !!
  function floyd_warshall(W)
    implicit none

    integer, intent(in)  :: W(:,:)
    integer, allocatable :: floyd_warshall(:,:)
    integer :: i, j, k, n

    n = size(W, 1)
    allocate(floyd_warshall(n, n))  ! ポインタでなければdeallocateする必要はないらしい
    floyd_warshall = W              ! Wに対して、破壊的代入を行ってもまあいいとおもう

    do k = 1, n
       do i = 1, n
          do j = 1, n
             ! 任意の整数a!=infに対してa+inf=inf+a=infを仮定しているのでこれはパス
             if ((floyd_warshall(i, k) .eq. inf) .or. (floyd_warshall(k, j) .eq. inf)) cycle

             floyd_warshall(i, j) = min(floyd_warshall(i, j), (floyd_warshall(i, k) + floyd_warshall(k, j)))
          end do
       end do
    end do
    
  end function floyd_warshall
  
end module module_floyd_warshall



!!**********************************************************************
!! main program
!!**********************************************************************

program main
  use module_floyd_warshall
  implicit none

  integer :: i, j, k, n, m, e, t
  integer, allocatable :: W(:,:), D(:, :), C(:)
  integer :: answer

  read(*,*) n
  allocate(W(n, n), D(n, n), C(n))
  

  do i = 1, n
     read(*, *) C(i)
     do j = 1, n
        W(i, j) = inf  !すべての要素をinfで初期化
     end do
     W(i, i) = 0       ! 対角成分は必ず0
  end do

  read(*, *) m
  do k = 1, m
     read(*, *) i, j, e
     W(i+1, j+1) = e   ! 1-based
     W(j+1, i+1) = e   ! 無向グラフなので対称性がある
  end do


  D = floyd_warshall(W)

  answer = inf
  do i = 2, n - 1
     do j = 2, n - 1
        if (i .eq. j) cycle
        t = D(1, i) + D(i, j) + D(j, n) + C(i) + C(j)
        answer = min(answer, t)
     end do
  end do
  
  write(*, '(I0)') answer
end program main