#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 105

struct Edge{
	Edge(int arg_to,int arg_a,int arg_b,int arg_d){
		to = arg_to;
		a = arg_a;
		b = arg_b;
		d = arg_d;
		cost = BIG_NUM;
	}
	int to,a,b,d,cost;
};

struct State{
	State(int arg_node_id,int arg_sum_dist){

		node_id = arg_node_id;
		sum_dist = arg_sum_dist;

	}
	bool operator<(const struct State &arg) const{

		return sum_dist > arg.sum_dist; //総距離の降順(PQ)
	}

	int node_id,sum_dist;
};

int V,E;
int start,goal;
int FROM,TO;
int FLOW;
int min_dist[NUM];
int table_1[NUM][NUM],table_2[NUM][NUM],table_3[NUM][NUM];
vector<Edge> G[NUM];


void dijkstra(){

	//コストを計算する
	for(int i = 0; i < V; i++){
		for(int k = 0; k < G[i].size(); k++){

			if(FLOW <= G[i][k].d){

				G[i][k].cost = G[i][k].a*FLOW;

			}else{

				G[i][k].cost = (FLOW-G[i][k].d)*G[i][k].b+G[i][k].a*G[i][k].d;
			}
		}
	}

	for(int i = 0; i < V; i++){

		min_dist[i] = BIG_NUM;
	}

	min_dist[start] = 0;
	priority_queue<State> Q;

	Q.push(State(start,0));

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().node_id]){

			Q.pop();

		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){

				int next_node = G[Q.top().node_id][i].to;
				int next_cost = Q.top().sum_dist+G[Q.top().node_id][i].cost;

				if(min_dist[next_node] > next_cost){

					min_dist[next_node] = next_cost;
					Q.push(State(next_node,next_cost));
				}
			}

			Q.pop();
		}
	}
}

void init(int table[NUM][NUM]){

	for(int i = 0; i < V; i++){
		for(int k = 0; k < V; k++){
			if(k != i){
				table[i][k] = BIG_NUM;
			}else{
				table[i][k] = 0;
			}
		}
	}
}

void calc_cost(int table[NUM][NUM],int base_flow,int table_index){

	for(int i = 0; i < V; i++){
		for(int k = 0; k < G[i].size(); k++){

			int cost;

			if(base_flow <= G[i][k].d){

				cost = G[i][k].a*base_flow;

			}else{

				cost = (base_flow-G[i][k].d)*G[i][k].b+G[i][k].a*G[i][k].d;
			}

			if(i == FROM && G[i][k].to == TO){

				if(table_index == 2){ //a < bとなっている辺には流さない

					if(G[i][k].a < G[i][k].b){

						cost = BIG_NUM;
					}

				}else if(table_index == 3){ //a < bとなっている辺に流す

					if(G[i][k].a > G[i][k].b){

						cost = BIG_NUM;
					}
				}

			}

			table[i][G[i][k].to] = min(table[i][G[i][k].to],cost);
		}
	}
}

void warshall_floyd(int table[NUM][NUM]){

	for(int mid = 0; mid < V; mid++){
		for(int L = 0; L < V; L++){
			if(table[L][mid] == BIG_NUM)continue;
			for(int R = 0; R < V; R++){
				if(table[mid][R] == BIG_NUM)continue;

				table[L][R] = min(table[L][R],table[L][mid]+table[mid][R]);
			}
		}
	}
}

int main(){

	scanf("%d %d %d %d %d",&V,&E,&start,&goal,&FLOW);

	bool FLG = false;

	int from,to,a,b,d;


	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %d %d %d",&from,&to,&a,&b,&d);

		if(a < b){

			FLG = true;
			FROM = from;
			TO = to;
		}

		G[from].push_back(Edge(to,a,b,d));
	}

	dijkstra();

	if(!FLG){

		if(min_dist[goal] == BIG_NUM){

			printf("Impossible\n");

		}else{

			printf("%d\n",min_dist[goal]);
		}

		return 0;
	}

	//経路を分岐させる
	int ans = min_dist[goal];

	//FLOW流した場合のテーブル作成
	init(table_1);
	calc_cost(table_1,FLOW,1);
	warshall_floyd(table_1);

	for(int flow = 1; flow <= FLOW-1; flow++){ //流す配分を全通り試す:flow→a < bとなる辺に流す流量

		//FLOW-flow流した場合のテーブル作成
		init(table_2);
		calc_cost(table_2,FLOW-flow,2);
		warshall_floyd(table_2);


		//flow流した場合のテーブル作成
		init(table_3);
		calc_cost(table_3,flow,3);
		warshall_floyd(table_3);

		//分岐を全探索
		for(int mid_L = 0; mid_L < V; mid_L++){
			for(int mid_R = 0; mid_R < V; mid_R++){

				int cost_1 = table_1[start][mid_L];
				int cost_2 = table_2[mid_L][mid_R];
				int cost_3 = table_3[mid_L][mid_R];
				int cost_4 = table_1[mid_R][goal];

				if(cost_1 == BIG_NUM || cost_2 == BIG_NUM || cost_3 == BIG_NUM || cost_4 == BIG_NUM)continue;

				ans = min(ans,cost_1+cost_2+cost_3+cost_4);
			}
		}
	}

	if(ans == BIG_NUM){

		printf("Impossible\n");

	}else{

		printf("%d\n",ans);
	}

	return 0;
}



Measured memory_bytes: 3404