Path scheduling for two robots in an undirected weighted graph

See more:

C++

C

graph

There are two robots A and B moving in an undirected weighted graph G. Since both robots are controlled remotely, at any time, the distance between them must be larger than a positive integer r (the distance between two robots is the length of the shortest path between two vertices that each robot stays at).

Originally, robot A stays at vertex a and robot B stays at vertex b. There are two treasures, each located at vertex c and vertex d. Robot A has to go to vertex c to collect a treasure. Similarly, robot B will go to vertex d to collect a treasure.

Schedule a sequence of moves for both robot, such that: there can only be one robot moving at a time (both robots don't move simultaneously); every move is performed on one edge only (which means when a robot makes a move, it can only go to one of its adjacent vertex only); the sequences end if robot A is at vertex c and robot B is at vertex d.
If there are no such sequences, print "IMPOSSIBLE" to the screen.

INPUT:

The first line contains the total number of vertices n (n<100) and total number of edges m
The following m lines contain 3 positive integers x, y, z indicating there is an edge of weight z between vertex x and vertex y.
The next 2 lines each contain 2 integers a, b and c, d where a, b are the starting points of each robot, and c, d are the end points of each robot.
The last line contains the positive integer r (both robots must always stay from each other at a distance larger than r).

OUTPUT:

If there is a sequence satisfying the above conditions, print to the screen lines, where each line contains two integers u and v indicating the position of two robots at each move (the vertices where each robot stays at). Else, print "IMPOSSIBLE".

SAMPLE INPUT:

6 9
0 1 6
0 4 1
1 4 7
1 2 1
4 2 7
4 3 4
2 3 9
2 5 2
3 5 5
0 2
2 3
4

SAMPLE OUTPUT:

0 2
0 3
1 3
2 3

SAMPLE GRAPH[^]

What I have tried:

I tried to implement a brute-force approach, but it doesn't work for large n (n can be as large as 100). I learned about some basic graph search algorithms (BFS, DFS) and algorithms to compute shortest path (Dijistra). Is there another way to solve this problem?. This is an assignment, so I'd appreciate receiving hints on the problem, rather than a complete solution. Also, I come up with the title on my own, since I don't know what its actual name is, if this problem has already been discussed somewhere else, could anybody tell me its actual name so I can study it more thoroughly?

Sorry for my bad English (；⌣̀_⌣́)