#include using namespace std; struct edge { // Terminal vertex / Weight int v, w; edge(int v, int w) : v(v), w(w) {} }; struct state { // Brain half / Vertex int h, v; state(int h, int v) : h(h), v(v) {} state() : h(0), v(0) {} }; class compare_wstate { public: bool operator() (const pair &l, const pair &r) { return l.first > r.first; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin >> n >> m >> s >> t; // Reverse edges into each vertex. vector> reverse(n); vector adj(n, 0); while (m--) { int u, v, w; cin >> u >> v >> w; reverse[v].emplace_back(u, w); adj[u]++; } priority_queue< pair, vector>, compare_wstate> pq; vector> d(2, vector(n, -1)); // We want to reach {t, left half turn} and reason backwards, // Dijkstra-style. pq.push({d[0][t] = 0, state{0, t}}); pq.push({d[1][t] = 0, state{1, t}}); while (!pq.empty()) { int dst; state st; tie(dst, st) = pq.top(); pq.pop(); if (d[st.h][st.v] != dst) continue; for (const edge &e : reverse[st.v]) { int nd = dst + e.w; // Are we forced to move from e.v in state !st.h ? if (st.h == 0) { // always move, we are in st.h = 1 in e.v if (d[1][e.v] >= 0 && d[1][e.v] <= nd) continue; d[1][e.v] = nd; pq.push({nd, state{1, e.v}}); } else { // only move if forced, we are in st.h = 0 in e.v adj[e.v]--; d[0][e.v] = max(nd, d[0][e.v]); if (adj[e.v] == 0) { pq.push({d[0][e.v], state{0, e.v}}); } } } } // We start in {0, s}. if (d[0][s] < 0 || adj[s] > 0) cout << "infinity" << endl; else cout << d[0][s] << endl; return 0; }