#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
#include <bitset>
#include <stack>

using namespace std;
using ll = long long;
using ull = unsigned long long;


const int MN = 110;
const ll INF = 1LL<<55;

struct E {
    int t;
    ll a, b, d;
    ll cost(ll f) {
        if (f <= d) return a*f;
        return a*d + b*(f-d);
    }
};
vector<E> g[MN];
vector<E> rg[MN];

void solve(int s, int f, ll dp[], bool rev = false) {
    if (f == 0) {
        fill_n(dp, MN, 0);
        return;
    }
    fill_n(dp, MN, INF);
    using P = pair<ll, int>;
    priority_queue<P, vector<P>, greater<P>> q;
    q.push(P(0, s));
    dp[s] = 0;
    while (!q.empty()) {
        P p = q.top(); q.pop();
        if (dp[p.second] < p.first) continue;
        auto gp = (!rev) ? g[p.second] : rg[p.second];
        for (E e: gp) {
            if (p.first+e.cost(f) < dp[e.t]) {
                dp[e.t] = p.first+e.cost(f);
                q.push(P(p.first+e.cost(f), e.t));
            }
        }
    }
}

int main() {
    int n, m, s, t;
    ll f;
    cin >> n >> m >> s >> t >> f;
    int exc_s = -1;
    E exc;
    for (int i = 0; i < m; i++) {
        int s, t;
        ll a, b, d;
        cin >> s >> t >> a >> b >> d;
        if (a < b) {
            exc_s = s;
            exc = E{t, a, b, d};
        } else {
            g[s].push_back(E{t, a, b, d});
            rg[t].push_back(E{s, a, b, d});
        }
    }
    ll re = INF;
    if (exc_s != -1) {
        static ll dp0[MN], dp1[MN], dp2[MN], dp3[MN], dp4[MN];
        solve(s, f, dp0);
        solve(t, f, dp1, true);
        for (int i = 0; i <= f; i++) {
            solve(exc_s, i, dp2, true);
            solve(exc.t, i, dp3);
            for (int x = 0; x < n; x++) {
                solve(x, f-i, dp4);
                for (int y = 0; y < n; y++) {
                    re = min(re, exc.cost(i)+dp0[x]+dp1[y]+dp2[x]+dp3[y]+dp4[y]);
                }
            }
        }
    } else {
        static ll dp[MN];
        solve(s, f, dp);
        re = dp[t];
    }
    if (re >= INF/2) {
        cout << "Impossible" << endl;
    } else {
        cout << re << endl;
    }
    return 0;
}