#include<iostream>
#include<fstream>
using namespace std;
int f[201],a[201][201],g[201][201];
int main()
{
	ifstream fin("cost.in");
	ofstream fout("cost.out");
	int i,j,k,s,u,v,n,m,oil,temp,x,y,z;
	fin>>n>>m>>u>>v>>s;
	for(i=1;i<=n;i++)
		fin>>f[i];
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>z;
		if(a[x][y]!=0||z<a[x][y])
			a[x][y]=z;
	}
	g[0][u]=f[u];
	for(i=0;i<=s;i++)
		for(j=1;j<=n;j++)
			if(g[i][j]!=0)
				for(k=1;k<=n;k++)
				{
					if(a[j][k]!=0)
					{
						oil=i+a[j][k];
						if(oil<=s)
						{
							if(g[i][j]<f[k])
								temp=f[k];
							else
								temp=g[i][j];
							g[oil][k]=temp;
						}
					}
				}
    int minn=99999999;
	for(i=0;i<=s;i++)
	{
		if(minn>g[i][v]&&g[i][v]!=0)
			minn=g[i][v];
	}
	if(minn==99999999)
		minn=-1;
	fout<<minn<<endl;
	return 0;
}