(n,),(c,),_,*s=$<.map{|l|l.split.map &:to_i} d=(0..n).map{[M=$$**9]*-~c} d[1][0]=0 s.transpose.sort.map{|s,t,y,m|y.upto(c){|j|d[t][j]=[d[t][j],d[s][j-y]+m].min}} p -~d[n].min%-~M-1