#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("auto2.in");
ofstream cout ("auto2.out");
struct bla
{
    int nod,urm,ore,st;
} t[1010];
struct bla_again
{
    int timp,varf;
} coada[500010];
int n,m,start,finish,parcare[110],time,taxa[110][110][110],sol[110][110];
void read ()
{ int a,b,d,k=0;
    cin>>n>>m>>start>>finish>>time;
    for(int i=1;i<=n;i++)
        cin>>parcare[i];
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>d;
        t[++k].nod=b; t[k].urm=t[a].st; t[k].ore=d; t[a].st=k;
        t[++k].nod=a; t[k].urm=t[b].st; t[k].ore=d; t[b].st=k;
        for(int j=0;j<time;++j) cin>>taxa[a][b][j];
    }
}
void init ()
{
    for(int i=1;i<=n;i++)
        if(i!=start)
        for(int j=0;j<=time;++j)
            sol[i][j]=INT_MAX;
}
void ford ()
{
    int pi=0,ps=1;
    for(int i=0;i<=time;++i) coada[++pi].varf=start,coada[pi].timp=i;
    while(ps<=pi)
    {
        int x=t[coada[ps].varf].st;
        while(x)
        {
            int lim=coada[ps].timp+t[x].ore;
            for(int i=lim;i<=time;++i)
            {
                int cod=sol[coada[ps].varf][coada[ps].timp]+t[x].ore*taxa[coada[ps].varf][t[x].nod][coada[ps].timp]+parcare[t[x].nod]*(i-lim);
                if(cod<sol[t[x].nod][i]) sol[t[x].nod][i]=cod,coada[++pi].varf=t[x].nod,coada[pi].timp=i;
            } x=t[x].urm;
        }  ++ps;
    }
}
void write ()
{ int maxim=INT_MAX;
    for(int i=0;i<=time;++i)
        if(sol[finish][i]<maxim) maxim=sol[finish][i];
    cout<<maxim;
}
int main()
{
    read();
    init();
    ford();
    write();
    cin.close();
    cout.close();
    return 0;
}