The Leverrier-Fadeev algorithm for a triangular matrix ? No kidding !
Here $N(x)=Adjoint(xI-A)$. It suffices to inverse a triangular matrix; cf. this algorithm, the complexity of which, is $\approx n^3/3$:
http://www.iaeng.org/publication/WCE2012/WCE2012_pp100-102.pdf
Yet, here, we multiply polynomials in $K[x]$ and not only elements in $K$.