#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,a[2502],x,y,dis[2502],ma,maxi[2502][3],b[2502][2502],vis[2502];
vector<ll>v[2502];
queue<ll>q;
void bfs(ll p){
	q.push(p);
	while(!q.empty()){
		ll K=q.front();
		q.pop();
		for(int i=0;i<v[K].size();i++){
			if(vis[v[K][i]]==0&&v[K][i]!=p){
				vis[v[K][i]]=1;
				b[p][v[K][i]]=b[p][K]+1;
				b[v[K][i]][p]=b[p][K]+1;
				q.push(v[K][i]);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	freopen("holiday3.in","r",stdin);
	//freopen("holiday3.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=2500;i++){
		for(int l=1;l<=2500;l++){
			b[i][l]=-1;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		b[x][y]=0;
		b[y][x]=0;
	}
	for(int i=1;i<=n;i++){
		for(int l=1;l<=n;l++)vis[l]=0;
		vis[i]=1;
		bfs(i);
	}
	for(int i=2;i<=n;i++){
		for(int l=2;l<=n;l++){
			if(l==i)continue;
			if(b[1][i]<=k&&b[i][l]<=k){
				if(maxi[l][0]==0)maxi[l][0]=i;
				else if(maxi[l][1]==0)maxi[l][1]=i;
				else if(maxi[l][2]==0)maxi[l][2]=i;
				else{
					if(a[maxi[l][0]]<=a[maxi[l][1]]&&a[maxi[l][1]]<=a[maxi[l][2]]&&a[i]>a[maxi[l][0]])maxi[l][0]=i;//123
					if(a[maxi[l][0]]<=a[maxi[l][2]]&&a[maxi[l][2]]<=a[maxi[l][1]]&&a[i]>a[maxi[l][0]])maxi[l][0]=i;//132
					if(a[maxi[l][1]]<=a[maxi[l][0]]&&a[maxi[l][0]]<=a[maxi[l][3]]&&a[i]>a[maxi[l][1]])maxi[l][1]=i;//213
					if(a[maxi[l][2]]<=a[maxi[l][0]]&&a[maxi[l][0]]<=a[maxi[l][1]]&&a[i]>a[maxi[l][2]])maxi[l][2]=i;//312
					if(a[maxi[l][2]]<=a[maxi[l][1]]&&a[maxi[l][1]]<=a[maxi[l][0]]&&a[i]>a[maxi[l][2]])maxi[l][2]=i;//321
					if(a[maxi[l][1]]<=a[maxi[l][2]]&&a[maxi[l][2]]<=a[maxi[l][0]]&&a[i]>a[maxi[l][1]])maxi[l][1]=i;//231
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int l=0;l<=2;l++)cout<<maxi[i][l]<<' ';
		cout<<'\n';
	}
	for(int B=2;B<=n;B++){
		for(int C=B+1;C<=n;C++){
			if(b[B][C]>k)continue;
			for(int j=0;j<3;j++){
				if(maxi[B][j]==0)continue;
				for(int h=0;h<3;h++){
					ll A=maxi[B][j],D=maxi[C][h];
					if(D==0||b[C][D]>k||b[A][B]>k)continue;
					if(A!=D&&A!=B&&A!=C&&D!=B&&D!=C){
						ma=max(ma,a[B]+a[C]+a[A]+a[D]);
						if(a[B]+a[C]+a[A]+a[D]==3886)
						cout<<A<<' '<<B<<' '<<C<<' '<<D<<"     "<<a[B]+a[C]+a[A]+a[D]<<'\n';
					}
				}
			}
		}
	}
	cout<<ma;
	return 0;
};