//#include #include using namespace std; typedef long long ll; const int INF = 1e9; const ll LINF = ll(1e18); const int MOD = 1000000007; const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; #define yes cout << "Yes" << endl #define YES cout << "YES" << endl #define no cout << "No" << endl #define NO cout << "NO" << endl #define rep(i, n) for (int i = 0; i < n; i++) #define ALL(v) v.begin(), v.end() #define debug(v) \ cout << #v << ":"; \ for (auto x : v) \ { \ cout << x << ' '; \ } \ cout << endl; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } //cout< P; struct graph { ll V; vector> G; vector d; //vector count;経路の本数 //vector prev; // prev[v] := v から復元できる辺たち graph(ll n) { init(n); } void init(ll n) { V = n; G.resize(V); d.resize(V); //count.resize(V); rep(i, V) { d[i] = LINF; //count[i] = 0; } } void add_edge(ll s, ll t, ll cost) { edge e; e.to = t, e.cost = cost; G[s].push_back(e); } void dijkstra(ll s) { rep(i, V) { d[i] = LINF; //count[i] = 0; } d[s] = 0; //count[s] = 1; priority_queue, greater

> que; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); ll v = p.second; if (d[v] < p.first) continue; for (auto e : G[v]) { if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); //count[e.to] = count[v]; // 復元のための //prev[e.to]=v; } /* else if (d[e.to] == d[v] + e.cost) { count[e.to] += count[v]; count[e.to] %= MOD; } */ } } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, m, p, q, t; cin >> n >> m >> p >> q >> t; p--; q--; graph g(n);//0 graph g1(n);//p graph g2(n);//q rep(i, m) { ll temp, temp1, temp2; cin >> temp >> temp1 >> temp2; temp1--; temp--; g.add_edge(temp, temp1, temp2); g.add_edge(temp1, temp, temp2); g1.add_edge(temp, temp1, temp2); g1.add_edge(temp1, temp, temp2); g2.add_edge(temp, temp1, temp2); g2.add_edge(temp1, temp, temp2); } g.dijkstra(0); ll sum = g.d[p]; g1.dijkstra(p); sum+=g1.d[q]; ll ans=-1; g2.dijkstra(q); sum+=g2.d[0]; if (sum <= t) { cout << t << "\n"; return 0; } rep(i,n){ ll temp=g.d[i]*2+max(g1.d[i],g2.d[i])*2; if(temp<=t){ chmax(ans,t-max(g1.d[i],g2.d[i])*2); } //cout<