#include <fstream>
#include <climits>
#include <cstdlib>

using namespace std;

unsigned short int p;
unsigned short int N, M;
unsigned short int A[6001], B[6001], D[6001];
unsigned short int dmax[801];

unsigned int * AA[801];
unsigned int matrix[801][801];
unsigned int sol[801], ion[801];
bool seen[801];
bool okay;
unsigned short int i, maximum, vsauce, first, last, node;
int insta;

unsigned int sol1, sol2;

int main ()
{
    ifstream fin ("dragoni.in");
    fin >> p;
    fin >> N >> M;
    for (i=1; i<=N; i++)
        fin >> dmax[i];
    for (i=1; i<=M; i++)
        fin >> A[i] >> B[i] >> D[i];
    fin.close();
    if (p == 1)
    {
        for (i=1; i<=M; i++)
            if (A[i] == 1)
                sol[B[i]] = D[i];
        for (i=1; i<=N; i++)
            if (sol[i] == 0)
                sol[i] = INT_MAX;
        while (okay == 0)
        {
            okay = 1;
            for (i=1; i<=M; i++)
                if (sol[B[i]] > sol[A[i]] + D[i])
                {
                    sol[B[i]] = sol[A[i]] + D[i];
                    okay = 0;
                }
        }
        for (i=1; i<=N; i++)
            if (sol[i] == INT_MAX)
                sol[i] = 0;
        maximum = sol[1];
        for (i=2; i<=N; i++)
            if (sol[i] > maximum && sol[i] <= dmax[1])
            {
                maximum = sol[i];
                vsauce = i;
            }
        sol1 = dmax[vsauce];
    }
    else
    {
        for (i=1; i<=N; i++)
        {
            AA[i] = (unsigned int *) realloc (AA[i], sizeof (unsigned int));
            AA[i][0] = 0;
        }
        for (i=1; i<=M; i++)
        {
            AA[A[i]][0]++;
            AA[A[i]] = (unsigned int *) realloc (AA[A[i]], (AA[A[i]][0]+1) * sizeof (unsigned int));
            AA[A[i]][AA[A[i]][0]] = B[i];
            AA[B[i]][0]++;
            AA[B[i]] = (unsigned int *) realloc (AA[B[i]], (AA[B[i]][0]+1) * sizeof (unsigned int));
            AA[B[i]][AA[B[i]][0]] = A[i];
        }
        for (i=1; i<=M; i++)
        {
            matrix[A[i]][B[i]] = D[i];
            matrix[B[i]][A[i]] = D[i];
        }
        first = last = 1;
        seen[first] = 1;
        ion[first] = 1;
        sol[first] = D[1];
        insta = dmax[1];
        while (first <= last)
        {
            node = B[first];
            first++;
            for (i=1; i<=AA[node][0]; i++)
                if (!seen[AA[node][i]] && insta > 0)
                {
                    seen[AA[node][i]] = 1;
                    sol[AA[node][i]] = sol[node] + matrix[AA[node][i]][node];
                    if (sol[AA[node][i]] <= insta)
                    {
                        insta -= (sol[AA[node][i]] - sol[node]);
                        if (insta <= 0)
                            insta = dmax[AA[node][i]];
                    }
                    else
                        insta = dmax[AA[node][i]];
                    last++;
                    B[last] = AA[node][i];
                }
        }
        sol2 = sol[N];
    }
    ofstream fout ("dragoni.out");
    if (p == 1)
        fout << sol1;
    else
        fout << sol2;
    fout.close();
    return 0;
}