#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __has_include() #include using namespace atcoder; #endif #if __has_include() #include using cpp_int=boost::multiprecision::cpp_int; #endif #if __has_include() #include templateusing cpp_float=boost::multiprecision::number>; templateusing cpp_double=boost::multiprecision::number>; #endif using namespace std; using ll=long long; #define read(x) cin>>(x); #define readll(x) ll (x);cin>>(x); #define readS(x) string (x);cin>>(x); #define readvll(x,N) vector (x)((N));for(int i=0;i<(N);i++){cin>>(x)[i];} #define rep(i,N) for(ll (i)=0;(i)<(N);(i)++) #define rep2d(i,j,H,W) for(ll (i)=0;(i)<(H);(i)++)for(ll (j)=0;(j)<(W);j++) #define is_in(x,y) (0<=(x) && (x) inline void erase_duplicate(vector& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());} inline ll powll(ll x,ll n){ll r=1;while(n>0){if(n&1){r*=x;};x*=x;n>>=1;};return r;} struct Edge{ ll from,to,cost; }; int main(){ ll N,M; cin>>N>>M; vector E(M+N); vector A(N); for(ll i=0;i>A[i]; E[i]={i,i+N,-A[i]}; } for(ll i=0;i>u>>v>>c; E[i+N]={u+N-1,v-1,c}; } const ll INF=numeric_limits::max(); vector d(2*N,INF); d[0]=0; for(ll i=0;i<2*N;i++){ for(Edge e:E){ if(d[e.from]==INF){ continue; } d[e.to]=min(d[e.to],d[e.from]+e.cost); } } for(Edge e:E){ if(d[e.from]==INF){ continue; } if(d[e.from]+e.cost