PROGRAMMING:Spring Tour

In the sunny spring, Xiao song suddenly wants to ride a bike outside the school to play, but there is more than one way to get to the destination. He wants to get to the destination as soon as possible, but he doesn't need to ride too far. Can you help him?
###Input format:
The input contains a test data, the first line has three integers n (2 < = n < = 1000), the number of possible locations on the way, and the location number 1 ~ n; M (1 < = m < = 10000) is the number of paths; D (2 < = d < = n), destination number; The school is the starting point, and the default value is 1. Next, line M: X, y, time dist, where x and y can reach each other, time and dist represent the time and distance from X to y or y to x respectively.
###Output format:
Output "time spent + space + distance to ride + space + path from school to destination" in the following format. The two places in the path are separated by an arrow (- >)（ See output sample for details)
###Input example:
Here is a set of inputs. For example:
```in
7 8 7
1 2 1 1
1 3 1 1
2 4 1 2
3 4 1 1
4 5 1 2
4 6 1 1
5 7 1 1
6 7 2 1
```
###Output example:
The corresponding output is given here. For example:
```out
4 5 1->3->4->5->7
```







answer：If there is no answer, please comment