旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

时间限制：1000

内存限制：65536

输入

输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0~(n-1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 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

样例输出

3 40

取帽子

拼题er们觉得戴帽子会令自己看上去很帅，所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅，服务员把他们的帽子收集了堆起来保管。当大家要离开的时候，发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队，使得每个人都能按顺序顺利取到自己的帽子。

已知每顶帽子的大小都不相同，并且帽子的尺寸跟帽子主人的体重有关 —— 越重的人戴的帽子就越大。

时间限制：1000

内存限制：65536

输入

输入第一行给出一个正整数 n (≤ 104)，为拼题er的人数。随后一行给出 n 个不同的帽子尺寸，为不超过 105 的正整数，顺序是从帽子堆的底部向上给出。最后一行给出 n 个不同的体重，顺序对应编号从 1 到 n 的拼题er。体重是不超过 106 的正整数。一行中的数字以空格分隔。

输出

在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 1 个空格分隔，行首尾不得有多余空格。

样例输入

10

12 19 13 11 15 18 17 14 16 20

67 90 180 98 87 105 76 88 150 124

样例输出

3 4 8 6 10 2 1 5 9 7

提示

样例说明： 第一顶帽子的尺寸是最大的 20，所以对应第 3 个人的最大体重 180，于是第 3 个人排在最前面。 第二顶帽子的尺寸是第 6 小的 16，对应第 6 小的体重 98，是第 4 个人，于是第 4 个人下一个走。 以此类推。

最短工期

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

时间限制：1000

内存限制：65536

输入

首先第一行给出两个正整数：项目里程碑的数量 N（≤ 100）和任务总数 M。这里的里程碑从 0 到 N-1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

样例输入

样例#1：

9 12

0 1 6

0 2 4

0 3 5

1 4 1

2 4 1

3 5 2

5 4 0

4 6 9

4 7 7

5 7 4

6 8 2

7 8 4

样例#2：

4 5

0 1 1

0 2 2

2 1 3

1 3 4

3 2 5

样例输出

样例#1：

18

样例#2：

Impossible

城市间紧急救援

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

时间限制：1000

内存限制：65536

输入

输入第一行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0 ~ (n-1)；m 是快速道路的条数；s 是出发地的城市编号；d是目的地的城市编号。 第二行给出 n个正整数，其中第 i 个数是第 i 个城市的救援队的数目，数字间以空格分隔。随后的 m 行中，每行给出一条快速道路的信息，分别是：城市 1、城市 2、快速道路的长度，中间用空格分开，数字均为整数且不超过 500。输入保证救援可行且最优解唯一。

输出

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 s 到 d 的路径中经过的城市编号。数字间以空格分隔。

样例输入

4 5 0 3

20 30 40 10

0 1 1

1 3 2

0 3 3

0 2 2

2 3 2

样例输出

2 60

0 1 3