//正确代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int oo = 2147483647;
struct Edge
{
int u, v, next;
long long cost, flow;
} edge[20100];
struct Path
{
int a, b, c;
} path[5010];
int p[maxn], prev[maxn];
long long d[maxn];
bool vis[maxn];
int tot;
queue<int> q;
void add(int u, int v, long long cost, long long flow)
{
edge[tot].u = u;
edge[tot].v = v;
edge[tot].cost = cost;
edge[tot].flow = flow;
edge[tot].next = prev[u];
prev[u] = tot ++;
}
void addEdge(int u, int v, long long cost, long long flow)
{
add(u, v, cost, flow);
add(v, u, -cost, 0);
}
bool spfa(int s, int t)
{
int u, v;
memset(vis, false, sizeof(vis));
memset(p, -1, sizeof(p));
fill(d, d + maxn, oo);
d[s] = 0;
vis[s] = true;
q.push(s);
while (!q.empty())
{
u = q.front();
for (int i = prev[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if (edge[i].flow && d[u] + edge[i].cost < d[v])
{
d[v] = d[u] + edge[i].cost;
p[v] = i;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
vis[u] = false;
q.pop();
}
return d[t] != oo;
}
long long MinCostMaxFlow(int s, int t, long long amount)
{
long long delta, flow = 0, ret = 0;
while (spfa(s, t))
{
delta = oo;
for (int i = p[t]; i != -1; i = p[edge[i].u])
delta = min(delta, edge[i].flow);
for (int i = p[t]; i != -1; i = p[edge[i].u])
{
edge[i].flow -= delta;
edge[i ^ 1].flow += delta;
}
flow += delta;
ret += delta * d[t];
}
if (flow == amount) return ret;
else return -1;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N, M;
int a, b, c;
int amount, cap;
long long result;
while (scanf("%d%d", &N, &M) != EOF)
{
for (int i = 1; i <= M; i ++)
scanf("%d%d%d", &path[i].a, &path[i].b, &path[i].c);
scanf("%d%d", &amount, &cap);
memset(prev, -1, sizeof(prev));
tot = 0;
addEdge(0, 1, 0, amount);
addEdge(N, N + 1, 0, amount);
for (int i = 1; i <= M; i ++)
{
addEdge(path[i].a, path[i].b, path[i].c, cap);
addEdge(path[i].b, path[i].a, path[i].c, cap);
}
result = MinCostMaxFlow(0, N + 1, amount);
if (result >= 0) printf("%lld\n", result);
else printf("Impossible.\n");
}
return 0;
}
//错误代码：
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <algorithm>
#include<queue>
#include<set>
#define LL long long
#define inf 2147483647
#define E 1e-7
#define M 20111
#define N 110
using namespace std;
int xx[M/4],yy[M/4];
struct Node
{
LL w,cap;
int u,v,next;
};
Node node[M];
int top;
int head[N];
int c[M/4];
int n,m,r,k;
LL d[N];
int p[N],s,t;
bool inq[N];
LL getflow()
{
LL ans=0;
int sss=0;
queue<int> q;
for(;;)
{
fill(d,d+t+1,inf);
memset(inq,0,sizeof(inq));
d[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u],v=node[i].v; i!=-1; i=node[i].next,v=node[i].v)
if(node[i].cap&&d[v]>d[u]+node[i].w)
{
d[v]=d[u]+node[i].w;
p[v]=i;
if(!inq[i])
{
inq[v]=1;
q.push(v);
}
}
}
if(d[t]==inf)
break;
int a=inf;
for(int i=p[t]; node[i].u!=s; i=p[node[i].u])
{
if(node[i].cap<a)
a=node[i].cap;
}
for(int i=p[t]; node[i].u!=s; i=p[node[i].u])
{
node[i].cap-=a;
node[i^1].cap+=a;
}
// for(int i=t;i!=s;i=node[p[i]].u)
// {
// node[p[i]].cap-=a;
// node[p[i]^1].cap+=a;
// }
sss+=a;
ans+=a*d[t];
}
if(sss==r)
{
return ans;
}
return -1;
}
void init()
{
memset(head,-1,sizeof(head));
top=0;
}
void addnode(int a,int b,int w,int c)
{
node[top].u=a;
node[top].v=b;
node[top].cap=c;
node[top].w=w;
node[top].next=head[a];
head[a]=top++;
node[top].v=a;
node[top].u=b;
node[top].cap=0;
node[top].w=-w;
node[top].next=head[b];
head[b]=top++;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in","r",stdin);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&xx[i],&yy[i],&c[i]);
}
scanf("%d%d",&r,&k);
init();
for(int i=1; i<=m; i++)
{
addnode(xx[i],yy[i],c[i],k);
addnode(yy[i],xx[i],c[i],k);
}
node[top].u=0;
node[top].v=1;
node[top].cap=r;
node[top].w=0;
node[top].next=head[0];
head[0]=top++;
node[top].u=n;
node[top].v=n+1;
node[top].cap=r;
node[top].w=0;
node[top].next=head[n];
head[n]=top++;
s=0;
t=n+1;
LL ans=getflow();
if(ans>0)
printf("%lld\n",ans);
else
printf("Impossible.\n");
}
return 0;
}