Roger와 Troy는 워털루 대학교에서 술래잡기 게임을 하고 있습니다. 워털루 대학교는 $N$개의 건물과 $M$개의 보도로 나타낼 수 있습니다. $i$번째 보도는 건물 $a_i$와 $b_i$를 연결하며 길이는 $d_i$ 미터입니다. 임의의 두 건물 사이에는 최대 1개의 보도가 존재합니다. 보도들은 서로 교차하지 않으며(즉, 건물에서만 다른 보도로 이동할 수 있습니다), 다리나 터널로 인해 평면상에 있지 않을 수도 있습니다. 어떤 건물에서 시작하더라도 보도를 따라 걸으면 다른 모든 건물에 도달할 수 있습니다.

Roger는 건물 1에서 술래잡기를 시작하며, 초당 최대 $v_1$ 미터의 속도로 걸을 수 있습니다. Roger는 건물에서 기다리거나 보도 위 어디에서든 기다릴 수 있습니다. Roger는 술래잡기 게임의 지속 시간을 최대화하는 방식으로 움직일 것입니다.

Troy는 건물 $x$를 선택하여 해당 건물에서 학생 그룹을 풀어놓습니다. 학생들은 모든 보도를 따라 초당 $v_2$ 미터의 속도로 퍼져 나갑니다. Troy의 학생들이 Roger에게 도달하면 술래잡기 게임은 종료됩니다.

각 건물 $x$에 대하여, 술래잡기 게임은 얼마나 오래 지속될까요?

입력

첫 번째 줄에는 4개의 정수 $N, M, v_1, v_2$가 공백으로 구분되어 주어집니다 ($2 \le N \le 2\,000$; $N-1 \le M \le 5\,000$; $1 \le v_1, v_2 \le 100$).

다음 $M$개의 줄에는 각각 3개의 정수가 주어지며, $i$번째 줄에는 $a_i, b_i, d_i$가 주어집니다 ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).

다음 표는 25점의 배점이 어떻게 분배되는지 보여줍니다.

출력

$N-1$개의 줄을 출력하십시오. $i$번째 줄에는 Troy가 건물 $i+1$에서 학생 그룹을 풀어놓았을 때의 술래잡기 게임 지속 시간을 초 단위로 출력해야 합니다. 지속 시간은 기약 분수 형태로 출력해야 합니다.

정수 $d$가 정수 $q$를 나누었을 때 나머지가 없으면 $d$는 $q$의 약수입니다. 정수 $z$가 $x$와 $y$ 모두의 약수이면 $z$는 $x$와 $y$의 공약수입니다. 분수 $x/y$가 기약 분수라는 것은 $y$가 양수이고, $x$와 $y$의 최대 공약수가 1임을 의미합니다.

예제

입력 1

3 2 1 10
1 2 135
1 3 15

출력 1

15/1
5/3

참고 1

$x=2$일 때, Roger는 건물 3으로 걸어가야 합니다. 15초 후, 학생들이 건물 3에서 Roger를 잡고 게임이 종료됩니다.

$x=3$일 때, Roger는 건물 2를 향해 걸어가야 합니다. 5/3초 후, 학생들이 건물 2와 3 사이의 보도에서 Roger를 잡고 게임이 종료됩니다. Roger는 1.666... 미터를 걸었고 학생들은 15 + 1.666... 미터를 이동했음에 유의하십시오.

입력 2

4 4 1 1
1 2 2
1 3 2
2 3 2
1 4 2

출력 2

4/1
4/1
5/1

참고 2

$x=2$일 때, Roger는 건물 4로 걸어가야 합니다.

$x=3$일 때, Roger는 건물 4로 걸어가야 합니다.

$x=4$일 때, Roger는 건물 2와 3 사이 보도의 중앙으로 걸어가야 합니다.