#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#define LL long longusing namespace std;const int N = 3000;struct edge{ int u,v,w,next;}e[N * 200];int head[N],tot,times[N],n,m;LL dis[N];bool inq[N];LL spfa(int source){ queue<int> q; memset(times,0,sizeof(times)); memset(dis,0xc0,sizeof(dis)); memset(inq,false,sizeof(inq)); q.push(source); inq[source] = true , dis[source] = 0; while(! q.empty()){ int u = q.front();q.pop(); // printf("u:%d dis:%I64d times:%dn",u,dis[u],times[u] + 1); if(++ times[u] > n) return -1; for(int i = head[u];i != -1;i = e[i].next){ int v = e[i].v; if(dis[v] < dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; if(! inq[v]) inq[v] = true , q.push(v); } } inq[u] = false; } return dis[n];}void add_edge(int u,int v,int w){ e[tot].u = u , e[tot].v = v , e[tot].w = w; e[tot].next = head[u] , head[u] = tot ++;}int main(){ while(scanf("%d%d",&n,&m) != EOF){ memset(head,-1,sizeof(head)); tot = 0; for(int i = 1;i <= n;i ++){ int cap; scanf("%d",∩); add_edge(i - 1,i,0); add_edge(i,i - 1,-cap); } for(int i = 1;i <= n;i ++) add_edge(0,i,0); for(int i = 1;i <= m;i ++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u - 1,v,w); } LL ans = spfa(0); if(ans == -1) puts("Bad Estimations"); else printf("%lldn",ans); } return 0;}
