N,*T=$<.map{|s|s.split.map &:to_i} g=->u{$*[u]||=(-2...a=/.$/=~"%b"%u).map{|b|u[b]<1?0:T[a][b]+g[1<