So I have been asking myself for a long time these 2 problems:

- Given a graph with N vertices and M edges, find the sum of shortest paths between (u -> v) for every u, v

- Given a graph with N vertices and M edges, answer queries asks for the shortest path between (u -> v)

It is guaranteed that there exists a way to travel from nodes to others.

Constraints: N <= 1e5 , M <= 1e5 , Q <= 1e5(Q is number of queries for the second problem)

Since then, I have been thinking and searching but nothing comes out good enough to pass the constraints.

Is there any way to solve these?