외판원 순회 로봇

$N$개의 도시와 이들을 잇는 단방향 도로로 이루어진 나라가 있다. 외판원은 가방에 든 로봇 한 대와 함께 도시들을 순회하려 한다.

외판원과 로봇은 $N$개의 도시 중 원하는 시작 도시에서 출발할 수 있다. 모든 도시는 외판원 또는 로봇이 적어도 한 번은 방문해야 순회를 마칠 수 있다. 순회를 시작할 때 로봇은 외판원의 가방 안에 있으며, 순회를 마칠 때도 로봇이 가방 안에 있어야 한다. 순회가 끝나는 도시는 시작 도시가 아니어도 된다.

외판원은 순회 중에 가방의 로봇을 꺼내 현재 도시에 놓을 수 있다. 놓인 로봇은 외판원이 실시간으로 조종할 수 있고, 로봇이 움직이는 동안 외판원도 자유롭게 움직일 수 있다. 외판원과 로봇은 매 순간 도로를 따라 이동하거나 도시에 멈춰 있을 수 있다. 외판원과 로봇이 어떤 도시에서 만나면 외판원은 로봇을 다시 가방에 넣을 수 있다. 로봇을 가방에서 꺼내거나 넣는 일은 도시에서만 할 수 있으며, 도로를 지나는 중에는 할 수 없다.

외판원은 로봇이 가방에 있는지와 관계없이 1미터를 이동하는 데 $U$의 시간이 걸린다. 놓인 로봇은 1미터를 이동하는 데 $V$의 시간이 걸린다. 로봇을 가방에서 꺼내거나 가방에 넣는 데는 시간이 걸리지 않는다.

도로망과 외판원, 로봇의 속도가 주어졌을 때, 외판원이 순회를 마치는 데 걸리는 최소 시간을 구하라.

첫 번째 줄에 도시의 수 $N$, 도로의 수 $M$, 외판원의 속도 $U$, 로봇의 속도 $V$가 공백으로 구분되어 주어진다. ($1\le N\le 12$; $0\le M\le 132$; $1\le U, V\le 100$)

두 번째 줄부터 $M$개의 줄에 걸쳐 도로 정보인 세 정수 $x$, $y$, $l$이 공백으로 구분되어 주어진다. 이는 $x$번 도시에서 $y$번 도시로 가는 길이 $l$미터의 도로가 있다는 뜻이다. ($x\ne y$; $1\le x,y\le N$; $1\le l\le 100$)

같은 출발점과 도착점을 잇는 도로는 두 번 이상 주어지지 않는다. 순회할 방법이 있는 경우에만 입력이 주어진다.

첫째 줄에 외판원과 로봇이 순회를 마치는 데 드는 최소 시간을 출력한다.