#include "bits/stdc++.h" /* #include "boost/multiprecision/cpp_int.hpp" namespace mp = boost::multiprecision; using i128=mp::cpp_int; */ using namespace std; typedef long long ll; typedef int64_t i64; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vll; typedef vector vvll; typedef vector vvvll; typedef vector vs; typedef vector vc; typedef vector vvc; typedef vector vd; typedef vector vvd; #define rep(i,a,n) for(int i=a;in;i--) #define yes(ans) if(ans)cout<<"yes"< que; que.push(s); while(1){ if(que.empty()) break; int r=que.front(); que.pop(); for(int i:miti[r]){ if(dist[i]==0){ que.push(i); dist[i]=1; } } } } //ベルマンフォード struct edges{ ll from; ll to; ll cost; }; using ve=vector; bool bellman(ve &miti,ll s,vll &dist,ll m,vll &cango){ //返り値 なし(副作用 distが変わる) dist[s]=0; ll y=1; ll cnt=0; while(y){ if(cnt>m){ return 1; } y=0; for(auto i:miti){ if(dist[i.from]+i.cost>n>>m; vll d(n); rep(i,0,n) cin>>d[i]; vvll doro(n,vll(0)); ve miti(m); ll a,b,c; rep(i,0,m){ cin>>a>>b>>c; a--; b--; doro[b].push_back(a); miti[i]={a,b,c-d[a]}; } vll cango(n); BFS(doro,n-1,cango); ve new_miti(0); rep(i,0,m){ if(cango[miti[i].from]==1&&cango[miti[i].to]==1) new_miti.push_back({miti[i]}); } vll dist(n,llINF); bool y=bellman(new_miti,0,dist,m,cango); if(y) cout<<"inf"<