#include<bits/stdc++.h>
using namespace std;
int p[100][100],h[100],v[100][100],truoc[100];

int main(){
	int n,dau,cuoi,step;
	cin>>n>>dau>>cuoi>>step;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>p[i][j];
		}
	}
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	bool check=false;
	stack<int> s;
	stack<int> ans;
	s.push(dau);
	int cost;
	while(check==false){
		int gn=0;
		cost=0;
		s.push(dau);
		while(!s.empty()){
		int gm,j;
		int t=s.top();s.pop();
		if(t==cuoi){
			check=true;
			cost+=p[truoc[cuoi]][cuoi];
			cout<<cuoi<<"->";
			int j=truoc[cuoi];
			while(j!=dau){
				cout<<j<<"->";
				j=truoc[j];
			}
			cout<<dau<<endl;
			cout<<"Tong chi phi:"<<cost;
			break;
		}
		
	
		for(int i=n-1;i>=0;i--){
			if(p[t][i]!=0  ){	
			 	gm= gn+p[t][i];
				int fm=gm+h[i];
				if(fm<=step){
					ans.push(i);
					s.push(i);
					truoc[i]=t;
	
					j=i;
					cost=fm;
				}
				
				
			}
		}
		gn+=p[t][j];
		}
		step+=step;
	}
	
}