void main(){ import std.stdio, std.string, std.conv, std.algorithm; int n, m, k, s, t; rd(n, m, k, s, t); s--; t--; auto as=new int[](m), from=new int[](m), to=new int[](m); foreach(i; 0..m) rd(as[i], from[i], to[i]), as[i]--, from[i]--, to[i]--; int[long] map; map[s]=0; map[(n-1)*k.to!long+t]=1; foreach(i; 0..m){ if((as[i]*k+from[i] in map)==null) map[as[i]*k.to!long+from[i]]=map.length.to!int; if(((as[i]+1)*k+to[i] in map)==null) map[(as[i]+1)*k.to!long+to[i]]=map.length.to!int; } import std.typecons; alias Edge=Tuple!(int, "to", int, "cost"); auto vmax=map.length; auto eds=new Edge[][](vmax, 0); foreach(i; 0..m){ auto u=map[as[i]*k+from[i]], v=map[(as[i]+1)*k+to[i]]; eds[u]~=Edge(v, 0); } auto blds=new int[][](n, 0); blds[0]~=s; blds[n-1]~=t; foreach(i; 0..m){ blds[as[i]]~=from[i]; blds[as[i]+1]~=to[i]; } foreach(i; 0..n){ auto b=blds[i]; sort(b); for(auto j=0, pre=-1; j=0){ auto u=map[i*k+b[pre]], v=map[i*k+b[j]]; auto d=b[j]-b[pre]; eds[u]~=Edge(v, d); eds[v]~=Edge(u, d); } pre=j; } } auto dist=new long[](vmax); const inf=1_000_000_000_000_000_000; fill(dist, inf); alias Node=Tuple!(int, "v", long, "d"); import std.container; auto Q=new BinaryHeap!(Array!Node, "a.d>b.d"); Q.insert(Node(map[s], 0)); dist[map[s]]=0; while(Q.length>0){ auto cur=Q.front; Q.removeFront; foreach(e; eds[cur.v]){ if(dist[e.to]<=dist[cur.v]+e.cost) continue; dist[e.to]=dist[cur.v]+e.cost; Q.insert(Node(e.to, dist[e.to])); } } auto d=dist[map[(n-1)*k+t]]; if(d