A max-plus matrix A is called weakly stable if the sequence (orbit) x, A circle times x, A(2)circle times x,... does not reach an eigenvector of A for any x unless x is an eigenvector. This is in contrast to previously studied strongly stable (robust) matrices for which the orbit reaches an eigenvector with any nontrivial starting vector. Max-plus matrices are used to describe multiprocessor interactive systems for which reachability of a steady regime is equivalent to reachability of an eigenvector by a matrix orbit. We prove that an irreducible matrix is weakly stable if and only if its critical graph is a Hamiltonian cycle in the associated graph. We extend this condition to reducible matrices. These criteria can be checked in polynomial time.