Ceste

어떤 나라에 도시 $N$개와 양방향 도로 $M$개가 있다. $i$번 도로를 달리면 $T_i$분이 걸리고 $C_i$쿠나가 든다. 쿠나는 크로아티아의 화폐 단위다.

당신은 $1$번 도시에서 출발한다. 어떤 경로로 이동할 때, 그 경로에 속한 도로의 $T_i$를 모두 더한 값을 총 시간, $C_i$를 모두 더한 값을 총 비용이라고 하자. 경로의 값은 총 시간과 총 비용을 곱한 값이다.

$1$번 도시를 제외한 각 도시마다, $1$번 도시에서 그 도시로 가는 경로의 값 중 최솟값을 구하라. 경로가 없으면 $-1$을 출력한다.

첫째 줄에 도시의 수 $N$ ($1 \le N \le 2000$)과 도로의 수 $M$ ($1 \le M \le 2000$)이 주어진다.

다음 $M$개 줄에는 각각 네 정수 $A_i$, $B_i$, $T_i$, $C_i$ ($1 \le A_i, B_i \le N$, $1 \le T_i, C_i \le 2000$)가 주어진다. 이는 $A_i$번 도시와 $B_i$번 도시를 잇는 도로가 있고, 이 도로를 달리는 데 $T_i$분과 $C_i$쿠나가 든다는 뜻이다.

두 도시를 잇는 도로가 여러 개일 수 있다. 자기 자신을 잇는 도로는 없다.

$N - 1$개 줄을 출력한다. $i$번째 줄에는 $1$번 도시에서 $i + 1$번 도시로 가는 경로의 값 중 최솟값을 출력한다. 두 도시가 연결되어 있지 않으면 $-1$을 출력한다.

두 번째 예제를 살펴보자.

$2$번 도시로 가려면 $1$번 도로를 달린다. $1$분과 $7$쿠나가 들므로 값은 $7$이다.

$3$번 도시로 가려면 $2$번 도로를 달린다. $3$분과 $2$쿠나가 들므로 값은 $6$이다.

$4$번 도시로 가려면 $2$번, $4$번, $5$번 도로를 순서대로 달린다. 모두 합쳐 $11$분과 $4$쿠나가 들므로 값은 $44$이다.