I cheated, and rather than doing a breadth first search, I simply used black magic:

dist startNode graph = dists where
    dists = map getDist graph
    getDist (Node n ns)
        | n == start = Z
        | otherwise = S . infMin . map ((dists !!) . subtract 1 . index) $ ns

So, infMin is just a specialized version of minimium :: Ord a => [a] -> a, that works even when a is potentially infinite, and the list is potentially empty. All we're saying is that the start node is distance zero (Z) and any other node is 1 more (S aka Successor) than the minimum distance of its neighbours. No need to check for disconnected components, they are simply an infinite distance away.

N.B. Declaring that the minimum of an empty list is in fact infinity allows the invariant:

min (infMin a) (infMin b) == infMin (a ++ b)

Which is handy.