1
#include<bits/stdc++.h>
using namespace std;
const int N = 2.5e3+9,M = 7e6+9;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k;
ll ans,a[N];
int h[N],ver[M],ne[M],idx;
queue<PII>q;
struct E
{
	int u,v;
}e[M];

int tot;

void add(int u,int v)
{
	idx++,ver[idx] = v,ne[idx] = h[u],h[u] = idx;
}

bool vis[N];
int dist[N][N];
vector<int> to[N];

void BFS(int X)
{
	queue<int> q1;
	memset(vis,0,sizeof vis);
	bool flag=false;
	q1.push(X);
	vis[X]=1;
	dist[X][X]=0;
	while(q1.size())
	{
		if(flag)break;
		int x=q1.front();
		q1.pop();
		for(int i=h[x];i;i=ne[i])
		{
			int y=ver[i];
			if(vis[y])continue;
			vis[y]=1;
			dist[X][y]=dist[X][x]+1;
			if(dist[X][y]>k+1)
			{
				flag=true;
				break;
			}
			to[X].push_back(y);
			q1.push(y);
		}
	}
}

ll dis[N][6];

bool inq[N][6];
int pre[N][6];

bool judge(int u,int d,int v)
{	
	if(d == 4 && v == 1)return 1;
	if(u == 0)return 1;
	if(u == v)return 0;
	return judge(pre[u][d],d-1,v);
}

void spfa()
{
	while(q.size())q.pop();
	q.push({1,0});
	inq[1][0] = 1;
	while(!q.empty())
	{
		int u = q.front().first,d = q.front().second;
		q.pop();inq[u][d] = 0;
		for(int i = 0;i<to[u].size();i++)
		{
			int v = to[u][i];
			if(!judge(u,d,v))continue;
			if(dis[v][d+1] < dis[u][d] + a[v])
			{
				pre[v][d+1] = u;
				dis[v][d+1] = dis[u][d] + a[v];
				if(!inq[v][d+1] && d+1 < 5)q.push({v,d+1}),inq[v][d+1] = 1;
			}
		}
		
	}
}

int main()
{
	
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 2;i <= n;i++)scanf("%lld",&a[i]);
	
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	
	for(int i = 1;i <= n;i++)
	{
		memset(vis,0,sizeof(vis));
		BFS(i);
	}
	
//	for(int i=1;i<=n;i++)
//	{
//		cout<<i<<" : ";
//		for(int j=0;j<to[i].size();j++)
//		{
//			cout<<to[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	spfa();

	printf("%lld",dis[1][5]);
	return 0;
}

2

#include<bits/stdc++.h>
using namespace std;
const int N = 2.5e3+9,M = 7e6+9;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k;
ll ans,a[N];
int h[N],ver[M],ne[M],idx;
queue<PII>q;

struct E
{
	int u,v;
}e[M];

int tot;

void add(int u,int v)
{
	idx++,ver[idx] = v,ne[idx] = h[u],h[u] = idx;
}

bool vis[N];

void bfs(int x)
{
	q.push({x,0});
	vis[x] = 1;
	while(!q.empty())
	{
		int u = q.front().first,d = q.front().second;q.pop();
		if(d >= k+1)break;
		for(int i = h[u];i;i = ne[i])
		{
			int v = ver[i];
			if(vis[v])continue;
			e[++tot].u = x,e[tot].v = v; 
			vis[v] = 1;
			q.push({v,d+1});
		}
	}
	while(q.size())q.pop();
}

ll dis[N][6];
bool inq[N][6];
int pre[N][6];

bool judge(int u,int d,int v)
{	
	if(d == 4 && v == 1)return 1;
	if(u == 0)return 1;
	if(u == v)return 0;
	return judge(pre[u][d],d-1,v);
}

void spfa()
{
	q.push({1,0});
	inq[1][0] = 1;
	while(!q.empty())
	{
		int u = q.front().first,d = q.front().second;
		q.pop();inq[u][d] = 0;
		for(int i = h[u];i;i = ne[i])
		{
			int v = ver[i];
			if(!judge(u,d,v))continue;
			if(dis[v][d+1] < dis[u][d] + a[v])
			{
				pre[v][d+1] = u;
				dis[v][d+1] = dis[u][d] + a[v];
				if(!inq[v][d+1] && d+1 < 5)q.push({v,d+1}),inq[v][d+1] = 1;
			}
		}
		
	}
}

int main()
{
	
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 2;i <= n;i++)scanf("%lld",&a[i]);
	
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	
	for(int i = 1;i <= n;i++)
	{
		memset(vis,0,sizeof(vis));
		bfs(i);
	}
	
	idx=0;
	memset(h,0,sizeof h);
	for(int i = 1;i <= tot;i++)add(e[i].u,e[i].v);
	
	spfa();

	printf("%lld",dis[1][5]);
	return 0;
}