n=gets
l=$<.map{|s|s.split.map &:to_i}
m=t=0;l.map{|e|t+=e[-1]}
d=[*(0..n.to_i-1)]
d.permutation.map{|a|
h=a.zip(d).to_h
s=t;l.take_while{|e|x,y,v=*e;s-=h[x]<h[y]?0:v;s>m};m=[m,s].max
}
p m