#8940. Travel Plan 普及+/提高

一张旅行者的地图给出了各个城市之间的公路距离，以及每条公路的费用。现在，你需要编写一个程序，帮助旅行者确定从起始城市到目的城市的最短路径。如果存在多

条最短路径，则输出总费用最小的那一条（题目保证这种情况下的路径是唯一的）。

输入包含一个测试用例。
第一行包含 4 个正整数 N、M、S、D，其中：

• N (≤500) 表示城市的数量（城市编号从 0 到 N−1）。
• M 表示公路的数量。
• S 和 D 分别表示起点城市和终点城市的编号。

接下来的 M 行，每行包含四个整数：

• City1 和 City2 是两个城市的编号，表示它们之间有一条公路。
• Distance 表示该公路的距离（整数，不超过 500）。
• Cost 表示该公路的费用（整数，不超过 500）。

所有整数之间用 空格 分隔。

输出一行，依次包含从起点到终点的城市编号（按照路径顺序），然后是最短路径的总距离和总费用。
所有数值之间用空格分隔，且行末无多余空格。

样例输入

复制4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

样例输出

复制0 2 3 3 40