Hello CodeForces!

Recently, I was participating in a gym contest, and came across a very interesting graph problem.

For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.

The graph does not contain self loops or multiple edges.

Here it is : http://mirror.codeforces.com/problemset/gymProblem/100917/F

After the contest, I did some googling, but I can only find re-search papers discussing very complex algorithms, I'm pretty sure the author did not intend these solutions.

My solution is as follows :

Let's say edge e connect vertices u and v. Remove edge e from the graph, then re-run dijikstra from u to v. If there exists a path, then there exists a simple cycle containing both u, and v.

Repeat for each edge, and minimise over the shortest cycle for each node.

The idea really makes sense, and the problem is the time limit verdict, how can I solve this problem more efficiently?

Please keep in mind that the graph is un-directed, ( the problem becomes easier in-case it is directed )