Problem link : this problem has made me scratch my head a lot .

The ideas i have tried and failed

1.Multisource bfs : can't find a way to get distances of a shop to other anime shops ,all non shop nodes are fine.

2.Tried finding if a node can be reached by two different shops ,but failed as my method leads to TLE and also if there are two cycles beginning from an anime shop and includes a node both times, then it failed my method.

3.To eliminate some sections ,used DSU to find components having only one anime shop , and solving them is easy , then proceeded to find MST of the graph by intuition ,but now i can't find what to do with MST and stuck here due to some cases like if there are two paths from one anime shop to other and one of them is direct connection, other is through a node in between them and say even if i found MST , what would I even do of that?

So these were my ideas, and i am done for so please give some hints to make me think in right direction like a topic required to solve it or something.