#include using namespace std; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i = (a); i != (b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) (v).begin(), (v).end() typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; const int maxn = 1e5; const int INF = 21e8; int N, M, S, T, indeg[maxn + maxn] = {}; vii E[maxn + maxn], RE[maxn + maxn]; int run() { vi d(N + N, INF); REP(i, N) d[i + i] = -INF; // maximizes time priority_queue pq; pq.emplace(-(d[T + T] = 0), T + T); // max had turn, but finishes pq.emplace(-(d[T+1+T] = 0), T+1+T); // min had turn, but finishes vector seen(N + N, false); while (!pq.empty()) { ii cur = pq.top(); pq.pop(); if (-cur.x != d[cur.y]) continue; // old edge assert(!seen[cur.y]); seen[cur.y] = true; if (cur.y & 1) { for (ii nxt : E[cur.y]) { int alt = nxt.y - cur.x; if (alt > d[nxt.x]) d[nxt.x] = alt; // last one to maximize over if (--indeg[nxt.x] == 0) pq.emplace(-d[nxt.x], nxt.x); } } else { for (ii nxt : E[cur.y]) { int alt = nxt.y - cur.x; // minimize version if (alt < d[nxt.x]) pq.emplace(-(d[nxt.x] = alt), nxt.x); } } } // WA: // d[S + S] != -INF is not a requirement of no answer. // It could be impossible to reach the entrance, // but we could have relaxed the d[S + S] once, but not all incoming arrows. return d[S + S] == -INF ? INF : d[S + S]; /* // flip value REP(i, N + N) if (!seen[i]) d[i] = INF; REP(i, N + N) { if (!seen[i]) continue; if ((i & ~1) == T + T) continue; int mval; if (i & 1) { // minimize mval = INF; for(ii nxt : RE[i]) if (seen[nxt.x]) mval = min(mval, d[nxt.x] + nxt.y); } else { // maximize mval = -INF; for(ii nxt : RE[i]) if (seen[nxt.x]) mval = max(mval, d[nxt.x] + nxt.y); } assert(mval == d[i]); } return d[S + S]; */ } int main() { srand(time(NULL)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> S >> T; REP(i, M) { // consider reverse edges! int u, v, t; cin >> v >> u >> t; E[u + u].eb(v + v + 1, t); indeg[v+1+v]++; E[u + u + 1].eb(v + v, t); indeg[v + v]++; int ww = v, w = u; RE[ww + ww].eb(w + w + 1, t); RE[ww + ww + 1].eb(w + w, t); } int answer = run(); if (answer == INF) cout << "infinity" << endl; else cout << answer << endl; return 0; }