#include <iostream>
#include<queue>
#include<vector>
#include<fstream>
using namespace std;
struct heap_node
{
    int nod,dist;
    bool  operator<(const heap_node &other) const
    {
        return dist>other.dist;
    }
};
struct edge
{
    int nod,dist,dragon;

};
const int NMAX=100000000;
priority_queue<heap_node>pq;
vector<vector<edge>>v;
vector<vector<int>>dist;
vector<int>dragoni;
void dijkstra()
{
    heap_node start_node;
    start_node.nod=1;
    start_node.dist=0;
    dist[1][1]=0;
    pq.push(start_node);
    while(!pq.empty())
    {
        edge frn;
        frn.nod=pq.top().nod;
        frn.dist=pq.top().dist;
        frn.dragon=dragoni[frn.nod];
        pq.pop()
        for(int i=0;i<v[frn.nod].size();i++)
        {
            if(frn.dragon>=v[frn.nod][i].dist && v[frn.nod][i].dist+frn.dist<dist[v[frn.nod][i]][frn.dragon])
            {
                if(frn.dragon<=dragon[v[frn.nod][i]])
                    frn.dragon=dragon[v[frn.nod][i]];
                dist[v[frn.nod][i]][frn.dragon]=v[frn.nod][i].dist+frn.dist;
                edge urm;
                urm.nod=v[frn.nod][i];
                urm.dist=dist[v[frn.nod][i]][frn.dragon];
                pq.push(urm);
            }
        }
    }
}
int main()
{
    int p,n,m;
    cin>>p;
    cin>>n>>m;
    v.resize(n+1);
    dist.resize(n+1);
    for(int i =0; i<n+1; i++)
    {
        dist[i].resize(n+1);
    }

    for(int i=1; i<=n; i++)
    {
        cin>>dragoni[i];
    }
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b>>c;
        edge val;
        val.nod=b;
        val.dist=c;
        v[a].push_back(val);
        val.nod=a;
        v[b].push_back(val);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dist[i][j]=NMAX;
        }
    }
    dijkstra();

}