#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], high[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; int ans = -INF; dp[0] = a[0]; rep(i, 2 * n) { rep(j, n) { rep(k, et[j].size()) { int u = j, v = et[j][k], c = ec[j][k]; int val = dp[u] + a[v] - c; if (v == n - 1 && dp[v] >= -INF / 2 && dp[v] < val && i >= n) { cout << "inf" << endl; return 0; } dp[v] = max(dp[v], val); } } ans = max(ans, dp[n - 1]); } cout << ans << endl; return 0; }