(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