#include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; const int INF = 1e+16; int n, m; int a[2500]; vector et[2500]; vector ec[2500]; int dp[2500]; signed main() { int i, j, k; cin >> n >> m; rep(i, n) cin >> a[i]; rep(i, m) { int u, v, c; cin >> u >> v >> c; u--; v--; et[u].push_back(v); ec[u].push_back(c); } rep(i, n) dp[i] = -INF; typedef pair P; priority_queue

que; int loopCnt = 0; que.push(P(a[0], 0)); while (!que.empty()) { P now = que.top(); que.pop(); int cst = now.first; int v = now.second; if (dp[v] >= cst) continue; dp[v] = cst; loopCnt++; if (loopCnt > 3 * n * n && v == n - 1) { cout << "inf" << endl; return 0; } for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; int nc = cst + a[nv] - ec[v][i]; if (dp[nv] < nc) { que.push(P(nc, nv)); } } } cout << dp[n - 1] << endl; return 0; }