#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=600;const int maxe=50000;const int INF=130000000;#define LL long longint n,m;int dis[maxn],pre[maxn],gap[maxn],arc[maxn],f[maxe],cap[maxe],first[maxn],next[maxe],vv[maxe],q[maxn];bool vis[maxn];int sap(int s,int t,int n,int is){ int j,mindis,ans=0,front=0,rear=1,u,v,low; bool found; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); memset(vis,0,sizeof(vis)); memset(arc,0,sizeof(arc));if(is) memset(f,0,sizeof(f)); q[0]=t;vis[t]=true;dis[t]=0;gap[0]=1; while(front<rear) { u=q[front++]; int e=first[u]; while(e) { v=vv[e]; if(!vis[v]) { dis[v]=dis[u]+1; vis[v]=true; q[rear++]=v; gap[dis[v]]++; arc[v]=first[v]; } e=next[e]; } } u=s;low=INF;pre[s]=s; while(dis[s]<n) { found=false; for(int &e=arc[u];e;e=next[e])if(dis[vv[e]]==dis[u]-1&∩[e]>f[e]) { found=true;v=vv[e]; low=low<cap[e]-f[e]?low:cap[e]-f[e]; pre[v]=u;u=v; if(u==t) { while(u-s) { u=pre[u]; f[arc[u]]+=low; f[arc[u]^1]-=low; } ans+=low;low=INF; } break; } if(found) continue; mindis=n; for(int e=first[u];e;e=next[e]) if(mindis>dis[vv[e]]&∩[e]>f[e]) { mindis=dis[vv[j=e]]; arc[u]=e; }; gap[dis[u]]--; if(gap[dis[u]]==0) return ans; dis[u]=mindis+1; gap[dis[u]]++; u=pre[u]; } return ans;}inline void add(int u,int v,int c,int &e){ next[e]=first[u],vv[e]=v,cap[e]=c,first[u]=e++; next[e]=first[v],vv[e]=u,cap[e]=0,first[v]=e++;}struct E{int u,v,l,h;}edge[maxe];int In[maxn],Out[maxn],flow[maxe];int solve(int n,int m,int s,int t){int i,j,e=2,ss=0;memset(first,0,sizeof(first));memset(In,0,sizeof(In));memset(Out,0,sizeof(Out));for(i=1;i<=m;i++){ if(edge[i].l>edge[i].h) return -1; In[edge[i].v]+=edge[i].l,Out[edge[i].u]+=edge[i].l,add(edge[i].u,edge[i].v,edge[i].h-edge[i].l,e),flow[i]=e-2;}for(i=1;i<=n;i++)add(n+1,i,In[i],e),add(i,n+2,Out[i],e),ss+=In[i];add(t,s,INF,e);j=sap(n+1,n+2,n+2,1);if(j<ss)return -1;j=f[e-2];cap[e-2]=f[e-2]=cap[e-1]=f[e-1]=0;j+=sap(s,t,n,0);return j;}struct node{ int u,v,w;}e[maxe];int s,t,p;int main(){ int ncase,l,r,i,j,u,v,w,bound; scanf("%d",&ncase); while(ncase--) { scanf("%d %d %d %d %d",&n,&m,&s,&t,&p); s++; t++; for(i=1;i<=m;++i)scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); bound=INF; for(i=1;i<=m;i++) edge[i].u=e[i].u+1,edge[i].v=e[i].v+1,edge[i].l=0,edge[i].h=e[i].w,bound=min(bound,e[i].w); int mf=solve(n,m,s,t); int l=0,r=mf+1; LL ans1,ans2,tmp; while(l<r) { int mid=(l+r)/2; tmp=mid; for(i=1;i<=m;i++) edge[i].h=min(e[i].w,mid); if(solve(n,m,s,t)==mf) ans1=tmp*p,r=mid; else l=mid+1; } l=0,r=mf+1; while(l<r) { int mid=(l+r)/2; tmp=mid; for(i=1;i<=m;i++){ edge[i].l=mid,edge[i].h=e[i].w; } if(solve(n,m,s,t)==mf) ans2=tmp*p,l=mid+1; else r=mid; } printf("%lld %lldn",ans1,ans2); }}
