翻译

有些公司将在Byteland举办公平的会议。Byteland的n个城镇，m条两镇之间的双向道路。当然，你可以使用道路从任一个城镇到达任何城镇。 有k种商品产自Byteland，并且每个城镇只生产一种类型。为了举办公平，你必须至少带来s种不同种类的商品。 【It costs d(u,v) coins to bring goods from town u to town v where d(u,v)d (u , v ) is the length of the shortest path from u to v .】 它花费货物从市区u到市区v的硬币成本为d（u，v），其中d（u，v）是从u到v的最短路的长度。 【Length of a path is the number of roads in this path.】 路径的长度是此路径中的道路数量。 主办单位将承担所有差旅费用，但他们可以选择城镇提货。现在他们想要计算在n个城镇举办公平的最低费用。 输入 城镇数量n，道路数量m，不同类型商品的数量k，持有公平所需的不同类型商品的数量s。 其中ai 是第i个城镇生产的商品类型。确保1和k之间的所有整数在整数ai中至少出现一次。 通过这条路相连的城镇。保证每两个城镇之间不超过一条公路。保证您可以通过道路从任何城镇到任何其他城镇。 打印n个数，其中第i个数是您需要花费在旅行费用上的最小数量的硬币用空格分隔数字。