#include #include #include #include using namespace std; using ll = int; // Dijkstra struct Edge{ int v; ll weight; }; // input edges struct S{ int u; bool b; }; struct PQ{ ll d; S v; }; // distance and target bool operator>(const PQ &l, const PQ &r){ return l.d > r.d; } ll dijkstra(const vector> &edges, const vector& deg, int s, S t) { array,2> dist; vector counts(edges.size()); dist[0].assign(edges.size(), 1e18); dist[1].assign(edges.size(), 0); priority_queue,greater> pq; dist[0][s] = dist[1][s] = 0; pq.push({0, {s, true}}); pq.push({0 ,{s, false}}); while (!pq.empty()) { ll d = pq.top().d; int u = pq.top().v.u; bool b = pq.top().v.b; pq.pop(); if(u == t.u && b == t.b) return d; if(d != dist[b][u]) continue; if(b) { for(auto &e : edges[u]) if (d + e.weight < dist[0][e.v]) pq.push({dist[0][e.v] = d + e.weight, {e.v, !b}}); } else { for(auto &e : edges[u]){ dist[1][e.v] = max(dist[1][e.v], d + e.weight); if(++counts[e.v] == deg[e.v]) pq.push({dist[1][e.v], {e.v, !b}}); } } } return -1; } int main(){ int n, m, s, t; cin >> n >> m >> s >>t; vector> g(n); vector deg(n); while(m--){ int u,v,w; cin >> u >> v >> w; g[v].push_back({u,w}); ++deg[u]; } auto d = dijkstra(g, deg, t, {s,true}); if(d >= 0) cout << d << endl; else cout << "infinity\n"; }