What would be a good data structure for a graph?

Question

So I'm supposed to make an app that demonstrates the small world problem, in 3 different functions. First to calculate the shortest path between each 2 Person, Second To calculate the number of movies each person appeared into, and Third to show the path for the shortest path. I'm reading this graph from a text file And it's format looks something like this:

 

Movie 0/Z/A

Movie 1/A/B/C

Movie 2/D/E/A/B

Movie 3/E/F/G

 

For the first function I build my graph as a dictionary that takes a string for the node (i.e A) and a hashset for its neighbors (i.e Z, B, C, D, E) so my data structure looked something like this (Dictionary < string , Hashset < string > > ) now for the second and third function I want to connect the nodes and the neighbors with the movies... So, the first thing I thought of was to make something like this ( Dictionary < string , Tuple < Hashset < string , Hashset < string > > > ) for which it's going to hold the nodes as strings, their neighbors as a Hashset, and the movies they appeared into as another hashset but I don't think it is efficient. My second thought was to make 2 dictionaries 1 for the nodes and its neighbors and another one for the node and the movies it appeared into. So my question is , Is there a better approach other than these two?