Let $v\_i$ be a vertex in a graph $G$ with vertices $(v\_1,...,v\_N) \in V$ and edges $(e\_1,...,e\_M) \in E$ with associated weights $(w\_1,...,w\_M)$. Let $v\_s \in V$ be specified vertex in the graph. In Mathematica 9, beyond repeatedly applying Dijkstra's algorithm by way of FindShortestPath[] and then summing the weights along the edges of each path, is there an efficient way to return the set of minimum costs to travel from $v\_s$ to all other vertices $v\_i \neq v\_s$?

Also, other than finding the maximum value of this matrix, is there an efficient way to detect if one path exists where the minimum cost exceeds some threshold $T$?