using System; using System.Collections.Generic; using System.Linq; using System.IO; using SB = System.Text.StringBuilder; //using System.Threading.Tasks; //using System.Text.RegularExpressions; //using System.Globalization; //using System.Diagnostics; using static System.Console; using System.Numerics; using static System.Math; using pair = Pair; class Program { static void Main() { //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false }); new Program().solve(); Out.Flush(); } readonly Scanner cin = new Scanner(); readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑ readonly int mod = 1000000007; readonly int dom = 998244353; bool chmax(ref T a, T b) where T : IComparable { if (a.CompareTo(b) < 0) { a = b; return true; } return false; } bool chmin(ref T a, T b) where T : IComparable { if (b.CompareTo(a) < 0) { a = b; return true; } return false; } bool complete(long[] s, long[] p, long[] q, long T, int P, int Q) { return (s[P] + p[Q] + q[0] <= T) || (s[Q] + q[P] + p[0] <= T); } bool cant(long[] s, long[] p, long[] q, long T, int P, int Q) { return (s[P] * 2 > T) || (s[Q] * 2 > T); } void solve() { int N = cin.nextint; int M = cin.nextint; int P = cin.nextint - 1; int Q = cin.nextint - 1; var T = cin.nextlong; var D = new Dijkstra(); var G = D.Input(N, M); var s = D.Run(G, 0); var p = D.Run(G, P); var q = D.Run(G, Q); //0->p->q->0 または 0->q->p->0とできるか if (complete(s, p, q, T, P, Q)) { WriteLine(T); return; } if (cant(s, p, q, T, P, Q)) { WriteLine(-1); return; } long ans = 0; for (int i = 0; i < N; i++) { long tmp = s[i] * 2; long finish = tmp + Max(p[i] * 2, q[i] * 2); if (finish > T) continue; chmax(ref ans, tmp + T - finish); } WriteLine(ans); } } class Dijkstra { public readonly long Inf; public Dijkstra(long Inf = long.MaxValue / 2) { this.Inf = Inf; } /// /// VertexとEdgeを兼ねる /// public struct Edge : IComparable { public int to; public long cost; public Edge(int to, long cost) { this.to = to; this.cost = cost; } public int CompareTo(Edge e) => cost.CompareTo(e.cost); } /// /// Dijkstraな入力を行う /// /// 頂点数 /// 辺数 /// 有向/無向 デフォルト: 無向 /// indexedの補正 デフォルト: 1 /// public List[] Input(int n, int m, bool dir = false, int indexed = 1, bool cost = true) { Scanner cin = new Scanner(); var ret = new List[n]; for (int i = 0; i < n; i++) { ret[i] = new List(); } for (int i = 0; i < m; i++) { int a = cin.nextint - indexed; int b = cin.nextint - indexed; var c = cost ? cin.nextlong : 1; ret[a].Add(new Edge(b, c)); if (!dir) ret[b].Add(new Edge(a, c)); } return ret; } public long[] Run(List[] edges, int s) { int n = edges.Length; var dist = new long[n]; var Q = new PriorityQueue(-1); for (int i = 0; i < n; i++) dist[i] = Inf; dist[s] = 0; Q.Enqueue(new Edge(s, dist[s])); while (Q.Any) { var p = Q.Dequeue(); var v = p.to; if (dist[v] < p.cost) continue; foreach (var e in edges[v]) { var d = p.cost + e.cost; if (d < dist[e.to]) { dist[e.to] = d; Q.Enqueue(new Edge(e.to, d)); } } } return dist; } /// /// 最短路 経路総数 Modとり /// /// /// /// /// /// public long[] Run(List[] edges, int s, out long[] cnt, long Mod) { int n = edges.Length; var dist = new long[n]; var Q = new PriorityQueue(-1); for (int i = 0; i < n; i++) dist[i] = Inf; dist[s] = 0; Q.Enqueue(new Edge(s, dist[s])); cnt = new long[n]; cnt[s] = 1; while (Q.Any) { var p = Q.Dequeue(); var v = p.to; if (dist[v] < p.cost) continue; foreach (var e in edges[v]) { var d = p.cost + e.cost; if (d < dist[e.to]) { dist[e.to] = d; cnt[e.to] = cnt[p.to]; Q.Enqueue(new Edge(e.to, d)); } else if (d == dist[e.to]) { cnt[e.to] = (cnt[e.to] + cnt[p.to]) % Mod; } } } return dist; } } /// /// Original Author: 蟻本 /// /// class PriorityQueue where T : IComparable { List heap; readonly int cmp; public PriorityQueue(int cmp = 1) { heap = new List(); this.cmp = cmp; } public void Enqueue(T x) { heap.Add(x); int i = Count++; while (i > 0) { int p = (i - 1) >> 1; if (x.CompareTo(heap[p]) * cmp <= 0) break; heap[i] = heap[p]; i = p; } heap[i] = x; } public T Dequeue() { T ret = heap[0]; T x = heap[--Count]; int i = 0; while ((i << 1) + 1 < Count) { int a = (i << 1) + 1; int b = (i << 1) + 2; if (b < Count && heap[a].CompareTo(heap[b]) * cmp < 0) a = b; if (x.CompareTo(heap[a]) * cmp >= 0) break; heap[i] = heap[a]; i = a; } heap[i] = x; heap.RemoveAt(Count); return ret; } public int Count { get; private set; } public bool Any => Count > 0; public T Peek() => heap[0]; } static class Ex { public static void join(this IEnumerable values, string sep = " ") => WriteLine(string.Join(sep, values)); public static string concat(this IEnumerable values) => string.Concat(values); public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); } public static int lower_bound(this IList arr, T val) where T : IComparable { int low = 0, high = arr.Count; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (arr[mid].CompareTo(val) < 0) low = mid + 1; else high = mid; } return low; } public static int upper_bound(this IList arr, T val) where T : IComparable { int low = 0, high = arr.Count; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (arr[mid].CompareTo(val) <= 0) low = mid + 1; else high = mid; } return low; } } class Pair : IComparable> where T : IComparable where U : IComparable { public T f; public U s; public Pair(T f, U s) { this.f = f; this.s = s; } public int CompareTo(Pair a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s); public override string ToString() => $"{f} {s}"; } class Scanner { string[] s; int i; readonly char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string[] scan => ReadLine().Split(); public int[] scanint => Array.ConvertAll(scan, int.Parse); public long[] scanlong => Array.ConvertAll(scan, long.Parse); public double[] scandouble => Array.ConvertAll(scan, double.Parse); public string next { get { if (i < s.Length) return s[i++]; string st = ReadLine(); while (st == "") st = ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return next; } } public int nextint => int.Parse(next); public long nextlong => long.Parse(next); public double nextdouble => double.Parse(next); }