#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], ndp[2500]; signed main() { int i, j, k; cin >> n >> m; assert(n <= 2500); assert(m <= 5000); rep(i, n) cin >> a[i]; rep(i, m) { int u, v, c; cin >> u >> v >> c; assert(1 <= u && u <= n); assert(1 <= v && v <= n); u--; v--; et[u].push_back(v); ec[u].push_back(c); } rep(i, n) dp[i] = -INF; rep(i, n) ndp[i] = -INF; int ans = -INF; dp[0] = 0; rep(i, 30 * n) { rep(j, n) { if (dp[j] <= -INF / 2) continue; rep(k, et[j].size()) { int u = j, v = et[j][k], c = ec[j][k]; int val = dp[u] + a[u] - c; if (val >= -INF / 2 && ndp[v] < val) { ndp[v] = val; } } } rep(j, n) dp[j] = ndp[j]; rep(j, n) ndp[j] = -INF; if (ans < dp[n - 1] + a[n - 1]) { ans = dp[n - 1] + a[n - 1]; if (i > 15 * n) { cout << "inf" << endl; return 0; } } } cout << ans << endl; return 0; }