解説

頂点を $L$ 倍してダイクストラ法を使うことで答えを $O((M + N)L \log(NL))$ で求めることができます。