Looking for algo/approach to solve this..

Given K friends location , M restaurants location and E edges. All the people are to meet at one restaurant, find the restaurant, where total travel distance from all people to that restaurant is the shortest among all restaurants. If no such resturant then return -1

Note:

• It is possible that thr is no edge for friends/resturants
• Numbers of edges are not fixed
• All inputs can be stored in memory

Example 1:

Intput:
Friends : 1, 2
Resturants: 5
Edges: (1,3) (2,3)

Output = -1

Example 2:

Intput:
Friends : 1, 2
Resturants: 2,3
Edges: (1,3) (2,3)

Output = 3 ( as 3 is closest to both 1 an 2 friends )

The problem can be solved with brute force with O(nme) complexity. Question is how to solve it faster than brute force.
Is graph right datastructure or we should use something else?
If you have seen this/similar problem earlier, please share its link . Thanks!