Find Best Path

You are given a directed graph with $N$ vertices (numbered $1$ through $N$) and $M$ weighted edges. For each vertex of the graph, find the minimum cost of a walk that passes through this vertex, or determine that the minimum does not exist, i.e. for any integer $m$, there is a walk with cost smaller than $m$. **Notes:** - A walk in a directed graph is a sequence of vertices $v_1, v_2, \ldots, v_K