The Leverrier-Faddeev 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$.

EDIT: answer to Michele. 1. The Leverrier-Faddeev algorithm has complexity $O(n^4)$ mult. in $K[x]$, that is $O(n^5)$ mult. in $K$. 

2. Of course, the complexity of the above cited method is $\approx n^4/3$ mult. in $K$.

3. About the instability, let $A\in M_n(\mathbb{Z})$, where the $a_{i,j}$ have $k$ digits; then some coefficients of the entries of $N(x)$ have almost $kn$ digits (see $N(x)[1,n]$). You have the same problem when you calculate the gcd of $2$ polynomials over $\mathbb{Z}$. If you work with finite-precision arithmetic, then of course there is a real risk.