#include <iostream>#include <cstring>#include <cstdio>#include <queue>#define N 1505#define inf 0x1f1f1f1f#define M 600100using namespace std;int cap[N][N], Dfn[N], Now[N];int gcnt;int in[N], out[N];int ghead[N], to[M], cc[M], nx[M], h[N], ff[M], nowf[M];bool vis[N];void Add(int l, int r, int c){to[gcnt] = r;nx[gcnt] = ghead[l];cc[gcnt] = c;ghead[l] = gcnt++;to[gcnt] = l;nx[gcnt] = ghead[r];cc[gcnt] = c;ghead[r] = gcnt++;}void add(int i, int j, int c) { cap[i][j]+=c; }int sour, tar;int ISAP(int n, int end, int flow){if (n==tar) return flow;int i, tab=end, vary, now=0;for (i=1; i<=end; i++)if (cap[n][i]){if (Dfn[n]==Dfn[i]+1)vary=ISAP(i,end,min(cap[n][i],flow-now)),cap[n][i]-=vary, cap[i][n]+=vary, now+=vary;if (Dfn[sour]==end) return now;if (cap[n][i]) tab=min(tab,Dfn[i]);if (flow==now) break;}if (now==0) {if (--Now[Dfn[n]]==0) Dfn[sour]=end; Now[Dfn[n]=tab+1]++;}return now;}int Maxflow(int s, int tar, int end){int flow=0; memset(Now, 0, sizeof(Now)), memset(Dfn, 0, sizeof(Dfn));for (Now[0]=end; Dfn[s]<end; ) flow+=ISAP(s, end, inf);return flow;}int main(){int tt, cal = 0, n, m, L, i;scanf("%d",&tt);while(tt--){if(cal++) puts("");memset(cap,0,sizeof(cap));gcnt = 0;memset(ghead, -1, sizeof(ghead));scanf("%d%d%d",&n,&m,&L);for(i=1;i<=n;++i){scanf("%d",&h[i]);if(h[i] == 1) sour = i;if(h[i] == L) tar = i;}for(i=1;i<=m;++i){int l, r, c;scanf("%d%d%d",&l,&r,&c);ff[i-1] = c;add(l,r,c);Add(l,r,c);}memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(nowf,0,sizeof(nowf));memset(vis,0,sizeof(vis));queue<int> q;q.push(sour);vis[sour] = 1;in[sour] = inf;while(!q.empty()){int s = q.front();int res = in[s];q.pop();for(i = ghead[s]; i != -1; i = nx[i]){if(i&1){continue;}int u = to[i];int fl = min(cc[i], res);out[s] += fl;in[u] += fl;nowf[i] += fl;res -= fl; if(!vis[u]) vis[u] = 1, q.push(u);}}memset(vis,0,sizeof(vis));while(!q.empty()) q.pop();q.push(tar);vis[tar] = 1;while(!q.empty()){int s = q.front();int del = in[s] - out[s];q.pop();for(i = ghead[s]; i != -1; i = nx[i]){if(i%2==0){continue;}int u = to[i];int fl = min(nowf[i^1], del);if(s != tar){ out[u] -= fl; in[s] -= fl; nowf[i^1] -= fl; del -= fl;} if(!vis[u]) vis[u] = 1, q.push(u);}} for(i=0;i<2*m;i+=2) cap[to[i^1]][to[i]] -= nowf[i];Maxflow(sour, tar, n);for(i=0;i<2*m;i+=2)printf("%dn", ff[i>>1] - cap[to[i^1]][to[i]]);}return 0;}
