using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; static class Program{ const int mod=(int)1e9+7; static List>[] li; static bool[] b; static void Main(){ Sc sc=new Sc(); int n=sc.I; int d=sc.I; int m=sc.I; li=new List>[n+1]; b=new bool[n+1]; var c=new long[n+1]; var g=new long[n+1]; for(int i=1;i<=n;i++){ li[i]=new List>(); c[i]=long.MaxValue; g[i]=long.MaxValue; } var sa=sc.Ia; var ta=sc.Ia; var ya=sc.Ia; var ma=sc.Ia; for(int i=0;i>(32); pq.Push(new Rheap>.Dt(0,Tuple.Create(1,0))); while(pq.cnt>0){ var e=pq.Dequeue; if(g[e.d.Item1]<=e.d.Item2){continue;} g[e.d.Item1]=e.d.Item2; b[e.d.Item1]=true; for(int i=0;id){continue;} if(!b[li[e.d.Item1][i].Item1]&&c[li[e.d.Item1][i].Item1]>li[e.d.Item1][i].Item2+e.n){ pq.Push(new Rheap>.Dt(li[e.d.Item1][i].Item2+e.n,Tuple.Create(li[e.d.Item1][i].Item1,e.d.Item2+li[e.d.Item1][i].Item3))); c[li[e.d.Item1][i].Item1]=li[e.d.Item1][i].Item2+e.n; } else if(g[li[e.d.Item1][i].Item1]>e.d.Item2+li[e.d.Item1][i].Item3){ pq.Push(new Rheap>.Dt(li[e.d.Item1][i].Item2+e.n,Tuple.Create(li[e.d.Item1][i].Item1,e.d.Item2+li[e.d.Item1][i].Item3))); } } } Console.WriteLine("{0}",c[n]==long.MaxValue?-1:c[n]); } } public class Rheap{ public class Dt{ public long n; public T d; public Dt(long n,T d){this.n=n;this.d=d;} public override string ToString()=>"d:"+d.ToString()+" n:"+n.ToString(); } private const int m=65; private long la=0; private Dt[][] bf; private int[] h; public int cnt=0; public Rheap(int max){ bf=new Dt[m][]; h=new int[m]; for(int i = 0;i0){ int p=0; for(int j = 1;jbf[i][j].n){p=j;} } la=bf[i][p].n; for(int j = 0;j(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i