using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; using static System.Console; using static System.Math; public class Solve{ static public int mod = 1000000007; static public string al = "abcdefghijklmnopqrstuvwxyz"; public static void Main(){ // 方針 // var towns = rint(); var money = rint(); var roads = rint(); var pass = new List>(); for(int i=0;i()); } var si = inta(); var ti = inta(); var price = inta(); var time = inta(); for(int i=0;i 0){ var de = pq.Dequeue(); var nowtime = de[0]; var nowprice = de[1]; var nowplace = de[2]; if(nowtime > min) continue; for(int i=0;i money || nt > min) continue; if(nt == towns-1){ min = Min(min,nti); continue; } pq.Enqueue(nti,np,nt); } } if(min > 1000000000){ WriteLine(-1); }else{ WriteLine(min); } } public static void swap(ref int a,ref int b){int temp = a;a= b;b = temp;} static void charswap(ref char a,ref char b){char temp = a;a= b;b = temp;} static int ncr(int n,int r){if(n=0;i--){if(binary[i] == '1'){value = value*a_power%mod;}a_power = a_power*a_power%mod;}return (int)value;} static int square2(int a,int b){long output = 1;var list = new List();int sh = 1;long n = a;list.Add(a);while(sh < b){sh *= 2;n = n*n%mod;list.Add(n);}for(int i=list.Count-1;i>=0;i--){if(b > sh){b -= sh;sh /= 2;output = output*list[i]%mod;}}return (int)output;} //各種読取 static string rstr(){ return ReadLine(); } static int rint(){ return int.Parse(ReadLine()); } static long rlong(){ return long.Parse(ReadLine()); } static string[] stra(){ return ReadLine().Split(' '); } static char[] chara(){ string[] a=stra();string b="";for(int i=0;i _priorityqueue = new List(); public void Enqueue(int a){ _priorityqueue.Add(a); int num = _priorityqueue.Count-1; while(true){ if(num == 0) break; if(_priorityqueue[(num-1)/2] < _priorityqueue[num]){ //大小逆の時弄るとこ int temp = _priorityqueue[(num-1)/2]; _priorityqueue[(num-1)/2] = _priorityqueue[num]; _priorityqueue[num] = temp; num = (num-1)/2; }else{ break; } } } public int Dequeue(){ int re = _priorityqueue[0]; int temp = _priorityqueue[0]; _priorityqueue[0] = _priorityqueue[_priorityqueue.Count-1]; _priorityqueue[_priorityqueue.Count-1] = temp; _priorityqueue.RemoveAt(_priorityqueue.Count-1); int num = 0; while(true){ int swapnum = -1; if((num+1)*2 < _priorityqueue.Count){ if(_priorityqueue[num*2+1] > _priorityqueue[(num+1)*2]){ //大小逆の時弄るとこ swapnum = num*2+1; }else{ swapnum = (num+1)*2; } }else if(num*2+1 < _priorityqueue.Count){ swapnum = num*2+1; } if(swapnum == -1) break; if(_priorityqueue[swapnum] > _priorityqueue[num]){ //大小逆の時弄るとこ temp = _priorityqueue[swapnum]; _priorityqueue[swapnum] = _priorityqueue[num]; _priorityqueue[num] = temp; num = swapnum; }else{ break; } } return re; } public int Peek(){ return _priorityqueue[0]; } public int Count(){ return _priorityqueue.Count; } } class PriorityQueue2{ private List _priorityqueue = new List(); private List _accompany_info = new List(); public void Enqueue(int a,int b){ _priorityqueue.Add(a); _accompany_info.Add(b); int num = _priorityqueue.Count-1; while(true){ if(num == 0) break; if(_priorityqueue[(num-1)/2] > _priorityqueue[num]){ //大小逆の時弄るとこ int temp = _priorityqueue[(num-1)/2]; _priorityqueue[(num-1)/2] = _priorityqueue[num]; _priorityqueue[num] = temp; temp = _accompany_info[(num-1)/2]; _accompany_info[(num-1)/2] = _accompany_info[num]; _accompany_info[num] = temp; num = (num-1)/2; }else{ break; } } } public int[] Dequeue(){ var re = new int[]{_priorityqueue[0],_accompany_info[0]}; var qcount = _priorityqueue.Count; var temp = _priorityqueue[0]; _priorityqueue[0] = _priorityqueue[qcount-1]; _priorityqueue[qcount-1] = temp; temp = _accompany_info[0]; _accompany_info[0] = _accompany_info[qcount-1]; _accompany_info[qcount-1] = temp; _priorityqueue.RemoveAt(qcount-1); _accompany_info.RemoveAt(qcount-1); int num = 0; while(true){ int swapnum = -1; if((num+1)*2 < _priorityqueue.Count){ if(_priorityqueue[num*2+1] < _priorityqueue[(num+1)*2]){ //大小逆の時弄るとこ swapnum = num*2+1; }else{ swapnum = (num+1)*2; } }else if(num*2+1 < _priorityqueue.Count){ swapnum = num*2+1; } if(swapnum == -1) break; if(_priorityqueue[swapnum] < _priorityqueue[num]){ //大小逆の時弄るとこ temp = _priorityqueue[swapnum];_priorityqueue[swapnum] = _priorityqueue[num];_priorityqueue[num] = temp; temp = _accompany_info[swapnum];_accompany_info[swapnum] = _accompany_info[num];_accompany_info[num] = temp; num = swapnum; }else{ break; } } return re; } public int[] Peek(){ var temp = new int[]{_priorityqueue[0],_accompany_info[0]}; return temp; } public int Count(){ return _priorityqueue.Count; } } class PriorityQueue3{ private List _priorityqueue = new List(); private List _accompany_info = new List(); private List _accompany_info2 = new List(); public void Enqueue(int a,int b,int c){ _priorityqueue.Add(a); _accompany_info.Add(b); _accompany_info2.Add(c); int num = _priorityqueue.Count-1; while(true){ if(num == 0) break; if(_priorityqueue[(num-1)/2] > _priorityqueue[num]){ //大小逆の時弄るとこ int temp = _priorityqueue[(num-1)/2]; _priorityqueue[(num-1)/2] = _priorityqueue[num]; _priorityqueue[num] = temp; temp = _accompany_info[(num-1)/2]; _accompany_info[(num-1)/2] = _accompany_info[num]; _accompany_info[num] = temp; temp = _accompany_info2[(num-1)/2]; _accompany_info2[(num-1)/2] = _accompany_info2[num]; _accompany_info2[num] = temp; num = (num-1)/2; }else{ break; } } } public int[] Dequeue(){ var re = new int[]{_priorityqueue[0],_accompany_info[0],_accompany_info2[0]}; var qcount = _priorityqueue.Count; var temp = _priorityqueue[0]; _priorityqueue[0] = _priorityqueue[qcount-1]; _priorityqueue[qcount-1] = temp; temp = _accompany_info[0]; _accompany_info[0] = _accompany_info[qcount-1]; _accompany_info[qcount-1] = temp; temp = _accompany_info2[0]; _accompany_info2[0] = _accompany_info2[qcount-1]; _accompany_info2[qcount-1] = temp; _priorityqueue.RemoveAt(qcount-1); _accompany_info.RemoveAt(qcount-1); _accompany_info2.RemoveAt(qcount-1); int num = 0; while(true){ int swapnum = -1; if((num+1)*2 < _priorityqueue.Count){ if(_priorityqueue[num*2+1] < _priorityqueue[(num+1)*2]){ //大小逆の時弄るとこ swapnum = num*2+1; }else{ swapnum = (num+1)*2; } }else if(num*2+1 < _priorityqueue.Count){ swapnum = num*2+1; } if(swapnum == -1) break; if(_priorityqueue[swapnum] < _priorityqueue[num]){ //大小逆の時弄るとこ temp = _priorityqueue[swapnum];_priorityqueue[swapnum] = _priorityqueue[num];_priorityqueue[num] = temp; temp = _accompany_info[swapnum];_accompany_info[swapnum] = _accompany_info[num];_accompany_info[num] = temp; temp = _accompany_info2[swapnum];_accompany_info2[swapnum] = _accompany_info2[num];_accompany_info2[num] = temp; num = swapnum; }else{ break; } } return re; } public int[] Peek(){ var temp = new int[]{_priorityqueue[0],_accompany_info[0],_accompany_info2[0]}; return temp; } public int Count(){ return _priorityqueue.Count; } }