1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
static const int64 INF = (int64)4e18;

struct Edge { int u, v; int64 w; };
struct Adj { int to; int id; int64 w; };

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M, S, T;
  if (!(cin >> N >> M >> S >> T)) return 0;

  vector<Edge> edges(M);
  vector<vector<Adj>> g(N + 1);
  for (int i = 0; i < M; ++i) {
    int u, v; int64 c;
    cin >> u >> v >> c;
    edges[i] = {u, v, c};
    g[u].push_back({v, i, c});
    g[v].push_back({u, i, c});
  }

  // 1) Dijkstra from T for dist[]
  vector<int64> dist(N + 1, INF);
  priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
  dist[T] = 0;
  pq.push({0, T});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;
    for (auto &e : g[u]) {
      int v = e.to; int64 nd = d + e.w;
      if (nd < dist[v]) {
        dist[v] = nd;
        pq.push({nd, v});
      }
    }
  }

  // 2) Build one shortest path tree (SPT) rooted at T
  vector<int> parent(N + 1, -1), depth(N + 1, 0);
  vector<vector<int>> tree(N + 1);
  vector<char> isTreeEdge(M, 0);

  for (int v = 1; v <= N; ++v) {
    if (v == T) continue;
    int p = -1, peid = -1;
    for (auto &e : g[v]) {
      if (dist[v] == dist[e.to] + e.w) { p = e.to; peid = e.id; break; }
    }
    if (p == -1) { cout << -1 << '\n'; return 0; }
    parent[v] = p;
    tree[p].push_back(v);
    isTreeEdge[peid] = 1;
  }

  // 3) Heavy-Light Decomposition (HLD) on SPT
  vector<int> sz(N + 1, 0), heavy(N + 1, -1);
  function<int(int)> dfs1 = [&](int u) {
    int maxSub = 0; sz[u] = 1;
    for (int v : tree[u]) {
      depth[v] = depth[u] + 1;
      int s = dfs1(v);
      sz[u] += s;
      if (s > maxSub) { maxSub = s; heavy[u] = v; }
    }
    return sz[u];
  };
  dfs1(T);

  vector<int> head(N + 1), pos(N + 1), invPos(N + 1);
  int curPos = 0;
  function<void(int,int)> dfs2 = [&](int u, int h) {
    head[u] = h; pos[u] = ++curPos; invPos[curPos] = u;
    if (heavy[u] != -1) dfs2(heavy[u], h);
    for (int v : tree[u]) if (v != heavy[u]) dfs2(v, v);
  };
  dfs2(T, T);

  auto lca = [&](int a, int b) {
    while (head[a] != head[b]) {
      if (depth[head[a]] > depth[head[b]]) a = parent[head[a]]; else b = parent[head[b]];
    }
    return depth[a] < depth[b] ? a : b;
  };

  // Segment tree: range chmin, point query
  struct Seg {
    int n; vector<int64> tag; Seg(int n=0): n(n), tag(4*n+4, INF) {}
    void range_chmin(int node, int l, int r, int ql, int qr, int64 v){
      if (ql>r || qr<l) return; if (ql<=l && r<=qr){ tag[node]=min(tag[node],v); return; }
      int m=(l+r)>>1; range_chmin(node<<1,l,m,ql,qr,v); range_chmin(node<<1|1,m+1,r,ql,qr,v);
    }
    void range_chmin(int l,int r,int64 v){ if(l>r) return; range_chmin(1,1,n,l,r,v);}    
    int64 point_query(int node,int l,int r,int idx,int64 acc){ acc=min(acc,tag[node]);
      if(l==r) return acc; int m=(l+r)>>1; return idx<=m?point_query(node<<1,l,m,idx,acc):point_query(node<<1|1,m+1,r,idx,acc);
    }
    int64 point_query(int idx){ return point_query(1,1,n,idx,INF);}  
  } seg(N);

  auto update_path_excl_target = [&](int u, int v, int64 val){
    while (head[u] != head[v]) {
      if (depth[head[u]] < depth[head[v]]) swap(u, v);
      seg.range_chmin(pos[head[u]], pos[u], val);
      u = parent[head[u]];
    }
    if (u == v) return;
    if (depth[u] < depth[v]) swap(u, v);
    seg.range_chmin(pos[v]+1, pos[u], val);
  };

  for (int i = 0; i < M; ++i) if (!isTreeEdge[i]) {
    int u = edges[i].u, v = edges[i].v; int64 val = dist[u] + edges[i].w + dist[v];
    int L = lca(u, v);
    update_path_excl_target(u, L, val);
    update_path_excl_target(v, L, val);
  }

  vector<int64> dist2_up(N + 1, INF);
  for (int u = 1; u <= N; ++u) if (u != T) {
    int64 mc = seg.point_query(pos[u]);
    dist2_up[u] = (mc >= INF/2) ? INF : (mc - dist[u]);
  }

  auto feasible = [&](int64 X){
    vector<int64> dX(N + 1, INF);
    priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> q;
    dX[S] = 0; q.push({0, S});
    while(!q.empty()){
      auto [du,u]=q.top(); q.pop(); if(du!=dX[u]) continue; if(du>X) continue; if(u==T) return true;
      for(auto &e: g[u]){
        int v=e.to; int64 cond2 = (parent[u]==v? dist2_up[u] : dist[u]);
        if (cond2 >= INF/2) continue; if (du + cond2 > X) continue; int64 nd = du + e.w;
        if (nd <= X && nd < dX[v]){ dX[v]=nd; q.push({nd,v}); }
      }
    }
    return false;
  };

  if (!feasible((int64)4e18/8)) { cout << -1 << '\n'; return 0; }

  int64 lo = dist[S], l = lo, r = max<int64>(lo, 1), hi;
  // exponential search for hi
  hi = r;
  while (!feasible(hi)) { if (hi > (int64)2e18) break; hi = min<int64>(hi*2+1, (int64)2e18); }
  if (!feasible(hi)) { cout << -1 << '\n'; return 0; }

  int64 ans = hi;
  while (l <= hi) {
    int64 mid = l + ((hi - l) >> 1);
    if (feasible(mid)) { ans = mid; hi = mid - 1; }
    else l = mid + 1;
  }
  cout << ans << '\n';
  return 0;
}