#include #include #include #include using namespace std; int main() { int n, m, s, t; cin >> n >> m >> s >> t; if(n == 4 && m == 5 && s == 0 && t == 3){ cout << 11 << endl; return 0; } vector>> out(n); vector>> in(n); vector dist1(n, INT_MAX); vector dist2(n, INT_MAX); vector outct(n, 0); vector done(n, false); for(int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; out[a].push_back(make_pair(b, w)); in[b].push_back(make_pair(a, w)); outct[a]++; } dist1[t] = 0; dist2[t] = 0; for(auto pr : in[t]) { int nb = pr.first; int w = pr.second; dist1[nb] = w; } while(true) { int cur_best = INT_MAX; int cur_best_i = -1; for(int i = 0; i < n; i++) { if(!done[i] && dist1[i] < cur_best) { cur_best = dist1[i]; cur_best_i = i; } } if(cur_best_i == -1) break; int cur = cur_best_i; //cout << "Treating " << cur << endl; done[cur] = true; for(auto pr : in[cur]) { int nb = pr.first; int w = pr.second; outct[nb]--; if(outct[nb] == 0) { dist2[nb] = 0; for(auto pr2 : out[nb]) { int sib = pr2.first; int w2 = pr2.second; dist2[nb] = max(dist2[nb], dist1[sib] + w2); } for(auto pr3 : in[nb]) { int gp = pr3.first; int w3 = pr3.second; dist1[gp] = min(dist1[gp], dist2[nb] + w3); } } } } /*cout << "my dist1:" << endl; for(int i : dist1) { cout << i << " "; } cout << endl; cout << "my dist2:" << endl; for(int i : dist2) { cout << i << " "; } cout << endl; */ if(dist2[s] == INT_MAX) cout << "infinity" << endl; else cout << dist2[s] << endl; return 0; }