1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 #include "set"
 13 #include "utility"
 14 using namespace std;
 15 typedef pair<int, int> pii;
 16 #define pb push_back
 17 #define mp make_pair
 18 #define fi first
 19 #define se second
 20 #define sof(x) sizeof(x)
 21 #define lc(x) (x << 1)
 22 #define rc(x) (x << 1 | 1)
 23 #define lowbit(x) (x & (-x))
 24 #define ll long long
 25 #define maxn 1550
 26 #define maxm 1000000
 27 const int inf = 1 << 30;
 28 int n, m, s, t, l;
 29 int eh[maxn], low[maxn], dist[maxn], pre[maxn], cur[maxn], tot, cnt[maxn];
 30 pii p[maxn];
 31 int in[maxn], out[maxn];
 32 struct Edge {
 33     int u, v, cap, flow, next;
 34 }et[maxm];
 35 void init() {
 36     tot = 0;
 37     memset(eh, -1, sizeof(eh));
 38 }
 39 void add(int u, int v, int cap, int flow) {
 40     Edge e = {u, v, cap, flow, eh[u]};
 41     et[tot] = e;
 42     eh[u] = tot++;
 43 }
 44 void addedge(int u, int v, int cap) {
 45     add(u, v, cap, 0), add(v, u, 0, 0);
 46 }
 47 int isap(int s, int t, int n){
 48     int u, v, now, flow = 0;
 49     memset(dist, 0, sizeof(dist)); 
 50     memset(low, 0, sizeof(low));
 51     memset(cnt, 0, sizeof(cnt));
 52     for(u = 0 ; u <= n ; u ++) cur[u] = eh[u];
 53     low[s] = inf, cnt[0] = n, u = s;
 54     while(dist[s] < n) {
 55         for(now = cur[u]; now != -1; now = et[now].next)
 56             if(et[now].cap - et[now].flow && dist[u] == dist[ v = et[now].v ] + 1 ) break;
 57         if(now != -1) {
 58             cur[u] = pre[v] = now;
 59             low[v] = min(et[now].cap - et[now].flow, low[u]);
 60             u = v;
 61             if(u == t) {
 62                 for(; u != s; u = et[pre[u]].u){
 63                     et[pre[u]].flow += low[t];
 64                     et[pre[u]^1].flow -= low[t];
 65                 }
 66                 flow += low[t]; low[s] = inf;
 67             }
 68         } else {
 69             if(--cnt[dist[u]] == 0) break;
 70             dist[u] = n, cur[u] = eh[u];
 71             for(now = eh[u]; now != -1; now = et[now].next)
 72                 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
 73                     dist[u] = dist[ et[now].v ] + 1;
 74             cnt[dist[u]]++;
 75             if(u != s) u = et[pre[u]].u;
 76         }
 77     }
 78     return flow;
 79 }
 80 
 81 void greedy() {//贪心初始流
 82     memset(in, 0, sizeof(in));
 83     memset(out, 0, sizeof(out));
 84     in[s] = inf;
 85     sort(p + 1, p + 1 + n);
 86     for(int i = 1; i <= n; i++) {
 87         for(int j = eh[p[i].se]; j != -1; j = et[j].next) {
 88             if(et[j].cap > 0) {
 89                 int dd = min(et[j].cap, in[p[i].se] - out[p[i].se]);
 90                 out[p[i].se] += dd;
 91                 in[et[j].v] += dd;
 92             }
 93         }
 94     }
 95     memset(in, 0, sizeof(in));
 96     in[t] = inf;
 97     for(int i = n; i >= 1; i--) {
 98         for(int j = eh[p[i].se]; j != -1; j = et[j].next) {
 99             if(et[j].cap == 0) {
100                 int k = j ^ 1;
101                 int u = et[k].u, v = et[k].v;
102                 if(out[u] > in[u]) {
103                     int dd = min(out[u] - in[u], et[k].cap);
104                     dd = min(dd, in[v]);
105                     in[u] += dd;
106                     in[v] -= dd;
107                     et[k].flow += dd;
108                 }
109             }
110         }
111     }
112 }
113 int main() {
114     int T, u, v, w, level;
115     scanf("%d", &T);
116     while(T--) {
117         scanf("%d%d%d", &n, &m, &l);
118         init();
119         for(int i = 1; i <= n; i++) {
120             scanf("%d", &level);
121             p[i] = mp(level, i);
122             if(level == 1) s = i;
123             else if(level == l) t = i;
124         }
125         for(int i = 0; i < m; i++) {
126             scanf("%d%d%d", &u, &v, &w);
127             addedge(u, v, w);
128         }
129         greedy();
130         isap(s, t, n);
131         for(int i = 0; i < m; i++) {
132             printf("%d\n", et[i<<1].flow);
133         }
134     }
135     return 0;
136 }
137