#include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template struct Edge { CostType cost; int src, dst; explicit Edge(const int src, const int dst, const CostType cost = 0) : cost(cost), src(src), dst(dst) {} auto operator<=>(const Edge& x) const = default; }; template struct BellmanFord { const CostType inf; std::vector dist; BellmanFord(const std::vector>>& graph, const CostType inf = std::numeric_limits::max()) : inf(inf), is_built(false), graph(graph) {} bool has_negative_cycle(const int s) { is_built = true; const int n = graph.size(); dist.assign(n, inf); dist[s] = 0; prev.assign(n, -1); for (int step = 0; step < n; ++step) { bool is_updated = false; for (int i = 0; i < n; ++i) { if (dist[i] == inf) continue; for (const Edge& e : graph[i]) { if (dist[e.dst] > dist[i] + e.cost) { dist[e.dst] = dist[i] + e.cost; prev[e.dst] = i; is_updated = true; } } } if (!is_updated) return false; } return true; } std::vector build_path(int t) const { assert(is_built); std::vector res; for (; t != -1; t = prev[t]) { res.emplace_back(t); } std::reverse(res.begin(), res.end()); return res; } private: bool is_built; std::vector prev; std::vector>> graph; }; int main() { int n, m; cin >> n >> m; vector A(n); for (int& A_i : A) cin >> A_i; vector>> graph(n); while (m--) { int a, b, c; cin >> a >> b >> c; --a; --b; graph[a].emplace_back(a, b, c - A[a]); } BellmanFord bellman_ford(graph); if (bellman_ford.has_negative_cycle(0)) { cout << "inf\n"; } else { cout << -bellman_ford.dist[n - 1] + (graph[n - 1].empty() ? A[n - 1] : 0) << '\n'; } return 0; }