소 운전한다.

소들은 날아다니는 대신 그냥 운전을 하기로 했다. 소들이 사는 대한민국에는 도시가 $V$개 있고, 두 도시를 양방향으로 잇는 고속도로가 $E$개 있다. 물론 소들은 선린인터넷고가 있는 $1$번 도시에 산다. 아, 이건 꿀팁인데, 모든 고속도로의 가운데에는 돈까스를 파는 휴게소가 하나씩 있다.

이제 휴가철이 되어서 소들이 여행을 떠난다. 여러분도 알다시피, 암소 베시는 다른 도시로 여행을 떠나려 한다. 베시는 고속도로들을 적절히 타고 이동해서 목적지에 도착할 것이다. 이 때, 경로를 잘 골라서 $1$번 도시에서 베시가 여행갈 도시까지 가는 데에 걸리는 시간의 최솟값을 구하라. 아, 어떤 도시로 여행갈 지는 비밀이다. 그러니 $2$번에서 $N$번까지의 각각의 도시에 대해, $1$번 도시에서 이 도시로 가는 데 걸리는 시간의 최솟값을 구하라.

... 그러나 베시는 문득 공허함을 느낀다. 베시는 이 문제가 '다익스트라 알고리즘'(Dijkstra algorithm)으로 너무 쉽게 풀린다는 사실도 알았을 뿐더러, 고속도로의 휴게소에서 파는 돈까스를 먹고 싶은 자신의 속마음을 알게 되었다. 베시는 모든 고속도로에 있는 돈까스를 모두 조사해, 돈까스의 맛을 수치화해 적어두었다. 베시는 휴가를 가는 경로에 있는 휴게소 가운데 정확히 한 곳에 들러서 돈까스를 사 먹을 것이다. 베시가 여행갈 수 있는 $2$번에서 $N$번까지의 각 도시에 대해, 경로와 들를 휴게소를 잘 골라서 $1$번 도시에서 이 도시로 가는 데 걸리는 시간에서 가는 도중에 휴게소를 적절히 하나 들러서 먹는 돈까스의 맛을 뺀 값의 최솟값을 구하라. 물론, 돈까스를 먹는 시간은 가는 데 걸리는 시간에 포함하지 않는다.

첫째 줄에는 대한민국에 있는 도시의 개수 $V$와 고속도로의 개수 $E$가 주어진다.

둘째 줄부터 $E$개의 줄에는 각각의 고속도로의 정보가 주어진다. 각 줄에는, 고속도로가 잇고 있는 두 도시 $x$, $y$, $x$에서 $y$로 가는 데 걸리는 시간 $t$, 휴게소에서 파는 돈까스의 맛을 나타내는 값 $k$가 차례대로 공백을 사이에 두고 주어진다.

같은 두 도시 쌍을 잇는 고속도로가 두 개 이상 있는 경우는 없다. 모든 도시들은 고속도로를 이용해 직, 간접적으로 연결되어 있다.

총 $V-1$개의 정수를 한 줄에 하나씩 출력한다. $i$번째로 출력하는 정수는, $1$번 도시에서 $i+1$번 도시에서 가는 데에 걸리는 시간에서 가는 도중에 먹는 돈까스의 맛을 뺀 값의 최솟값이다.

• $1 \le V \le 100,000$
• $1 \le E \le 100,000$
• $1 \le x \neq y \le V$
• $1 \le t \le 20,000$
• $1 \le k \le 1,000,000,000$