#include<bits/stdc++.h>
#define ll long long
#define M 505
#define inf 4557430888798830399
#define minf 0x3f
using namespace std;
ll n,m,x,u,v,l,c,ans=inf;
ll dis[M],vis[M],C[M];//4557430888798830399
struct line{
	ll v,l,c;
};
priority_queue<ll> q;
vector<line> edge[M];
void dijkstra(ll L){
	memset(dis,minf,sizeof dis);
	memset(vis,0,sizeof vis);
//	cout<<dis[1]<<' ';
	dis[1]=0;
	q.push(1);
	while(!q.empty()){
		u=q.top();
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto i : edge[u]){
			v=i.v,l=i.l,c=i.c;
			if(l<L) continue;
			if(dis[v]>dis[u]+c){
				dis[v]=dis[u]+c;
				q.push(v);
			}
		}
		vis[u]=0;
	}
}
int main(){
	cin>>n>>m>>x;
	for(ll i=1;i<=m;i++){
		cin>>u>>v>>l>>c;
		C[i]=c;
		edge[u].push_back({v,l,c});
		edge[v].push_back({u,l,c});
	}
	for(ll i=1;i<=m;i++){
		dijkstra(C[i]);
		for(ll j=1;j<=n;j++)
			cout<<dis[j]<<' ';
		cout<<endl;
		if(dis[n]!=inf)
			ans=min(ans,dis[n]+x/C[i]);
	}
	cout<<ans;
	return 0;
}