Dijikstra's algorithm with "hull" value catch
Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left.  Then, use Dijkstra's algorithm on that graph.  The graph can be built on the fly and does not need to be constructed explicitly.