1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000 14 #define maxm 100000 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27     int x=0,f=1;char ch=getchar(); 28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30     return x*f; 31 } 32 int  n,m,s,t,maxflow,tot=1,a[maxn],u[maxn],v[maxn],w[maxn],head[maxn],cur[maxn],h[maxn]; 33 queue<int>q; 34 ll d[2][maxn]; 35 bool vv[maxn],can[maxn]; 36 struct edge{int go,next,v;}e[maxm]; 37 void add(int x,int y,int v) 38 { 39     cout<<x<<‘ ‘<<y<<‘ ‘<<v<<endl; 40     e[++tot]=(edge){y,head[x],v};head[x]=tot; 41     e[++tot]=(edge){x,head[y],0};head[y]=tot; 42 } 43 void add2(int x,int y,int v) 44 { 45     e[++tot]=(edge){y,head[x],v};head[x]=tot; 46     e[++tot]=(edge){x,head[y],v};head[y]=tot; 47 } 48 bool bfs() 49 { 50     for(int i=s;i<=t;i++)h[i]=-1; 51     q.push(s);h[s]=0; 52     while(!q.empty()) 53     { 54         int x=q.front();q.pop(); 55         for(int i=head[x];i;i=e[i].next) 56          if(e[i].v&&h[e[i].go]==-1) 57          { 58             h[e[i].go]=h[x]+1;q.push(e[i].go); 59          } 60     } 61     return h[t]!=-1; 62 } 63 int dfs(int x,int f) 64 { 65     if(x==t) return f; 66     int tmp,used=0; 67     for(int i=cur[x];i;i=e[i].next) 68      if(e[i].v&&h[e[i].go]==h[x]+1) 69     { 70         tmp=dfs(e[i].go,min(e[i].v,f-used)); 71         e[i].v-=tmp;if(e[i].v)cur[x]=i; 72         e[i^1].v+=tmp;used+=tmp; 73         if(used==f)return f;        74     } 75     if(!used) h[x]=-1; 76     return used; 77 } 78 void dinic() 79 { 80     maxflow=0; 81     while(bfs()) 82     { 83         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 84     } 85 } 86 inline void dfss(int k,int x) 87 { 88     can[x]=1; 89     cout<<"AAAAA "<<x<<endl; 90     for4(i,x)if(e[i^k].v&&!can[y])dfss(k,y); 91 } 92 void spfa(int k,int s) 93 { 94     for (int i=1;i<=n;i++){vv[i]=0;d[k][i]=inf;} 95     q.push(s);d[k][s]=0;vv[s]=1; 96     while(!q.empty()) 97     { 98         int x=q.front();q.pop();vv[x]=0; 99         for (int i=head[x],y;i;i=e[i].next)100          if(e[i].v&&d[k][x]+(ll)e[i].v<d[k][y=e[i].go])101          {102             d[k][y]=d[k][x]+(ll)e[i].v;103             if(!vv[y]){vv[y]=1;q.push(y);}104          }105     }106 }107 int main()108 {109     freopen("input.txt","r",stdin);110     freopen("output.txt","w",stdout);111     int T=read();112     while(T--)113     {114         n=read();m=read();115         for1(i,n-1)a[i]=read();a[n]=inf;116         memset(head,0,sizeof(head));tot=0;117         for1(i,m){u[i]=read();v[i]=read();w[i]=read();add2(u[i],v[i],w[i]);}118         spfa(0,1);spfa(1,n);119         memset(head,0,sizeof(head));tot=1;120         for1(i,m)121         {122             if(d[0][u[i]]+w[i]+d[1][v[i]]==d[0][n])add(u[i],v[i],min(a[u[i]],a[v[i]]));123             if(d[0][v[i]]+w[i]+d[1][u[i]]==d[0][n])add(v[i],u[i],min(a[u[i]],a[v[i]]));124         }125         s=1;t=n;126         dinic();127         memset(can,0,sizeof(can));128         dfss(0,s);dfss(1,t);129         bool flag=0;130         for1(i,n)for4(j,i)131         {132           cout<<i<<‘ ‘<<e[j].v<<‘ ‘<<e[j].go<<‘ ‘<<can[e[j].go]<<‘ ‘<<a[i]<<‘ ‘<<a[e[j].go]<<endl;133           if((j&1)==0&&e[j].v==0&&a[i]==a[e[j].go])flag=1;134           if(!can[e[j].go])flag=1;135         }136         printf("%s %d\n",flag?"No":"Yes",maxflow);137     }    138     return 0;139 }

77 182379144 698428 938640 388960 540949 364019 923498 161083 379161 546263 67508 946028 763144 666174 774392 522287 160432 823294 541850 474678 933172 502667 320829 436050 397761 539493 411093 703802 730697 409152 880392 352439 615122 673569 419734 973775 671533 72899 333380 323169 860351 929091 765259 745904 432060 601993 620743 327315 253111 300079 401670 292384 846512 692952 80569 320062 374591 249920 359805 201500 688319 391428 223128 42918 350254 437724 880443 257608 426985 809968 573136 566946 925304 488503 464726 273522 70 76 50913523 12 23084071 44 92825870 38 19584760 15 3642285 8 91554314 9 65572166 74 8059939 15 82546775 28 77006962 17 86830677 39 71639222 45 64001129 31 73899235 68 49081769 66 2109827 24 79990643 15 74017223 76 56903344 62 90553063 45 36325164 25 7075240 37 2815634 62 84447871 52 23490377 41 43443038 4 5103838 71 58976547 63 21182921 60 51774012 10 49869625 70 64628245 69 29725635 19 16652739 76 16791154 75 34912847 38 9525362 76 70223458 63 90862563 53 39106411 38 9814737 15 604940 6 71027060 30 7634389 28 74678262 6 1442922 61 43486949 20 47638227 14 4461148 69 44221155 43 87251211 27 63170363 44 2213848 21 88961027 12 54062943 23 97096321 42 48800210 55 15196059 19 18997829 38 98506329 77 8537491 2 1425701 3 6292061 4 5706401 7 632721 13 5167141 16 8522351 18 1409471 19 1888351 20 8024821 26 2062731 32 4570011 33 5451401 36 3701521 46 3464291 50 8247951 51 5448731 56 9395091 57 8182241 65 5329321 67 6343131 72 6659971 73 9897871 61 269969272 41 243874169 8 87965467 62 168146025 77 74715619 75 383922141 17 7934167 20 16816946 70 93044133 38 5358838 42 94016969 12 30289019 69 185977716 42 30162002 51 40230320 40 201110650 6 150540751 45 120648332 69 159161111 21 22012632 4 42807020 75 322557432 20 3454814 57 24758411 9 13320359 42 135723020 27 100839173 54 338739733 3 8406677 43 65569335 77 231494673 44 42045651 66 171472165 38 54809132 31 234807762 48 17505036 5 347365768 39 110773767 29 143177336 41 273458633 47 6311364 49 70822436 13 14656260 17 4046856 60 220410257 34 234202716 48 163858820 70 47438835 61 247087464 31 8111741 48 236427953 28 147881849 45 47249233 12 180636270 9 12343359 30 139584462 21 106466013 10 233348456 25 98364333 20 2573427 56 87623741 28 15324968 58 145055114 17 132859526 53 15728961 51 41832970 29 78921632 45 129435558 5 154707946 37 243900326 3 4229333 76 115679914 15 92389927 55 119128539 29 11217023 40 45855067 73 35547473 60 215382470 53 50229918 43 318505453 54 259801537 42 10830033 64 136469868 15 193320449 28 19791239 15 2681782 15 263681357 17 236585527 60 133273818 71 219755476 39 16791120 41 23022562 31 26625083 53 114996359 24 48436550 60 231881664 42 187453159 50 44598268 24 16999