#include <iostream>#include <string>#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#include <cmath>#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))#define CL(a,b) memset(a,b,sizeof(a))#define inf 0x7fffffff#define LL long long int#define N (1<<11)#define M 101000using namespace std;int f[N][11];int ma[11][11];int val[11];void solve(int n,int broom,int eroom,int time){int i,j,k;for(i=0;i<(1<<n);i++)for(j=0;j<n;j++)f[i][j]=inf;f[(1<<broom)][broom]=0;int l;for(l=0;l<n;l++) for(i=0;i<(1<<n);i++) for(j=0;j<n;j++) if(i&(1<<j)) for(k=0;k<n;k++) if(ma[j][k]!=-1&&f[i][j]!=inf) f[i|(1<<k)][k]=MIN(f[i|(1<<k)][k],f[i][j]+ma[j][k]);int ans=0;for(i=0;i<(1<<n);i++){if(!(i&(1<<eroom)))continue;if(f[i][eroom]>time)continue;int sum=0;for(j=0;j<n;j++)if(i&(1<<j))sum+=val[j];ans=MAX(sum,ans);}printf("%dn",ans);}int main(){int n,m,t,i,j,k,x,y,broom,eroom;while(scanf("%d%d%d",&n,&m,&t)!=EOF){scanf("%d%d",&broom,&eroom);for(i=0;i<n;i++)scanf("%d",&val[i]);CL(ma,-1);for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&k);ma[x][y]=ma[y][x]=k;}solve(n,broom,eroom,t);}}
