#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <utility>
#include <cmath>
#include <cassert>
using namespace std;

#define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
#define pb push_back
#define mp make_pair
#define sz(a) (int)((a).size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn = 100005;
const int inf = 1000005000;

priority_queue<pii, vector<pii>, greater<pii> > q;
int n, m, s, t, k;
vector<pii> g[maxn];
int c[2*maxn], p[2*maxn];
int d[maxn];


int path(int s, int t, int w)
{
  forn (i, n) d[i] = inf;
  while (!q.empty()) q.pop();

//    printf("%d \n", sz(q));

  q.push(mp(d[s] = 0, s));


  while (!q.empty())
  {
    int dd = q.top().first, x = q.top().second;
    q.pop();

    if (dd > d[x]) continue;
    if (x == t) return d[x];

    forn (i, sz(g[x]))
    {
      int y = g[x][i].first, e = g[x][i].second;
      int cost = c[e] + p[e] * w;
//      printf("%d -> %d : %d\n", x, y, cost);
      if (d[y] > d[x] + cost)
        q.push(mp(d[y] = d[x]+cost, y));
    }

  }

  return inf;
}



int solve(int w)
{
  int res = path(s, t, w) + path(t, s, w);
//  printf("%d = %d\n", w, res);
  return res;
}
int main()
{
//  freopen("a.in", "r", stdin);

  scanf("%d %d %d %d %d", &n, &m, &s, &t, &k);
  --s, --t;
//  printf("%d %d\n", s, t);


  forn (i, m)
  {
    int x, y, c1, p1, c2, p2;
    scanf("%d %d %d %d %d %d", &x, &y, &c1, &p1, &c2, &p2);
    --x, --y;

    c[2*i] = c1,   p[2*i] = p1;
    c[2*i+1] = c2, p[2*i+1] = p2;
    g[x].pb(mp(y, 2*i));
    g[y].pb(mp(x, 2*i+1));
  }

///  puts("!!");

  int l = 0, r = k;

  while (r-l > 15)
  {
    int m1 = (2*l+r) / 3;
    int m2 = (l+2*r) / 3;

    int h1 = solve(m1);
    int h2 = solve(m2);

    if (h1 < h2) r = m2;
    else l = m1;
  }

  int res = inf;

  for (int i=l; i<=r; ++i)
    res = min(res, solve(i));

  printf("%d\n", res);



  return 0;
}