暂无测试数据。

在 A 国中，有 $n$ 个城市，编号为 $1$ 至 $n$。其中，有两个城市非常特殊——A 国的政治中心 $1$ 城，与经济中心 $2$ 城。

A 国有河流蜿蜒流过其中 $k$ 个城市，为编号 $n-k+1$ 至 $n$ 的城市，这 $k$ 个城市的水资源非常丰富。

A 国的某些地方群山环绕，绝巘林立，因此只有 $m$ 条可以修建水道的路径，第 $i$ 条路径连接第 $u_i$ 个城市与第 $v_i$ 个城市，修建的距离为 $d_i$。

众所周知，A 国的政治中心与经济中心的用水量极大，因此，国王想设计一种方案，从这 $k$ 个有河流流过的城市中引水入城，缓解政治中心与经济中心的用水压力。

具体地，国王需要在 A 国中修建一些水道，使得 $1$ 城与 $2$ 城均可通过水道与有河流流过的 $k$ 个城市其中至少一个相连。如果有水道连接第 $u$ 个城市与第 $v$ 个城市，那么修建这条水道的费用即为其距离。

由于政治中心与经济中心用水量巨大，因此仅仅从一个临河的城市通过水道调水可能不够。如果方案中政治中心与经济中心都仅能从同一座临河城市调水，那么需要一个额外的费用 $w$。

国王想知道，达成这个目标的最小费用是多少。如果无论如何都达成不了目标，请输出 inf。

输入格式

第一行四个正整数 $n,m,k,w$，表示城市数，可修建水道数，临河城市个数，以及额外费用。

接下来 $m$ 行，每行三个整数 $u_i,v_i,d_i$ 表示路径两端的城市编号，以及距离。

输出格式

输出一行，一个整数表示答案。

数据范围

子任务 1（$10\%$）：$1\leq k\lt n\leq 5$，$1\leq m\leq 15$。

子任务 2（$40\%$）：$1\leq k\lt n\leq 12$，$1\leq m\leq 150$。

子任务 3（$10\%$）：$1\leq n\leq 500$，$1\leq k\leq 10$，$1\leq m\leq 125000$，$w=0$。

子任务 4（$20\%$）：$1\leq n\leq 500$，$1\leq k\leq 10$，$1\leq m\leq 125000$。

子任务 5（$20\%$）：$1\leq n\leq 500$，$1\leq k\leq 20$。

对于全部数据，$1\leq u_i,v_i\leq n\leq 500$，$1\leq k\leq 20$，$2+k\leq n$，$1\leq m\leq 125000$，$0\leq d_i,w\leq 10^5$，可能有连接两个相同城市的不同路径。

3 3 1 5
1 2 3
1 3 5
2 3 1

9

4 2 1 5
1 2 3
2 3 1

inf