12.1.3

import java.util.ArrayList;
import java.util.Scanner;
import java.io.PrintWriter;

import static javafx.scene.input.KeyCode.V;

/**
 * Created by Сергей on 27.05.2016.
 */

//ИСПОЛЬЗУЕМ ТОТ ЖЕ АЛГОРИТМ ДЕЙСТРА, ИЗМЕНИМЛСЯ ЛИШЬ ФОРМАТ ВХОДНЫХ ДАННЫХ
public class Solution321 {
    public static void main(String Args[]){
        int INF = Integer.MAX_VALUE / 2;
        int arr [][];
        int dist[]; //массив для хранения расстояния от стартовой вершины
        boolean noUsed[]; //массив для хранения информации о пройденных и не пройденных вершинах
        int start,end; //стартовая,конечная вершины, от которой ищется расстояние до всех других
        Scanner sc=new Scanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);
        int min,minIndex;
        int n=sc.nextInt();
        //инициализация
        arr=new int[n][n];

        dist=new int[n];
        for (int i=0;i<n;i++)
            dist[i]=INF;

        noUsed=new boolean[n];
        for (int i=0;i<n;i++)
        {
            noUsed[i]=true;
        }


        int price[]=new int[n];// массив цен на бензин
        for (int i=0;i<n;i++)
            price[i]=sc.nextInt();

        int m;//колличество дорог
        m=sc.nextInt();
        int i1,j1;
        //заполним матриу смежности
        for (int ind=0;ind<m;ind++){
            i1=sc.nextInt();
            j1=sc.nextInt();
            i1--;
            j1--;
            arr[i1][j1]=price[i1];
            arr[j1][i1]=price[j1];
        }

        for (int i=0;i<n;i++)
         for (int j=0;j<n;j++) {
             if(arr[i][j]==0) arr[i][j]=-1;
         }
        for (int i=0;i<n;i++)
            arr[i][i]=0;

        //алгоритм дейстры
        dist[0] = 0;//расстояние до стартовой вершины равно 0
        int minindex,temp;
        do {
            minindex = 10000;//индекс след вершины
            min = 10000;//значение для поиска след вершины
            for(int i=0; i<n;i++) {
                if((noUsed[i] == true) && (dist[i]<min)) {
                    min = dist[i];
                    minindex = i;
                }
            }
            if(minindex != 10000) {
                for(int i=0;i<n;i++) {
                    if(arr[minindex][i] > 0) {
                        temp = min+arr[minindex][i];
                        if(temp < dist[i])
                            dist[i] = temp;
                    }
                }
                noUsed[minindex] = false;
            }
        } while(minindex < 10000);
        for (int i=0;i<n;i++)
        {if (dist[i]==INF) dist[i]=-1;}
        System.out.print(dist[n-1]);
        }
}