30709번 - 외판원 순회 로봇

문제

$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$)

출발점과 도착점이 모두 같은 도로가 두 번 이상 주어지지 않으며, 순회할 방법이 존재하는 경우만 입력으로 주어진다.

출력

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

제한

힌트