티켓 구매

인기 밴드 "Flayer"의 음악가들은 세계 투어로 "make their exit"할 예정이라고 발표했다. 물론 Berland도 방문할 것이다.

Berland에는 n개의 도시가 있다. 사람들은 양방향 열차 노선을 이용해 도시 사이를 이동할 수 있다. 노선은 정확히 m개이며, i-th 노선은 도시 vi에서 도시 ui로(그리고 ui에서 vi로) 이동하는 데 사용할 수 있고, 이 노선을 이용하는 비용은 wi코인이다.

각 도시는 "Flayer"의 방문을 받으며, i-th 도시의 공연 티켓 가격은 ai코인이다.

당신은 Berland의 모든 도시에 친구가 있으며, 친구들은 당신의 프로그래밍 실력을 알고 공연을 관람하기 위해 지불해야 하는 최소 코인 수를 계산해 달라고 부탁했다. 모든 도시 i에 대해, 도시 i의 사람이 어떤 도시 j로 이동하고(또는 도시 i에 머물 수도 있다), 그곳에서 공연을 관람한 뒤 도시 i로 돌아오는 데 지출해야 하는 최소 코인 수 (if j ≠ i)를 계산해야 한다.

형식적으로, 모든 에 대해 를 계산해야 한다. 여기서 d(i, j)는 도시 i에서 도시 j로 이동하는 데 지출해야 하는 최소 코인 수이다. 도시 i에서 도시 j에 도달할 방법이 없다면 d(i, j)는 무한히 큰 것으로 간주한다.

첫 번째 줄에 두 정수 n와 m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105)가 주어진다.

이어서 m개의 줄이 주어지며, i-th에는 i-th 열차 노선을 나타내는 세 정수 vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1012)가 주어진다. 같은 도시 쌍을 연결하는 중복 열차 노선은 없다. 즉, 각 (v, u)에 대해 추가적인 (v, u)와 (u, v) 중 어느 것도 입력에 존재하지 않는다.

다음 줄에는 n개의 정수 a1, a2, ... ak (1 ≤ ai ≤ 1012)가 주어진다. 이는 i-th 도시에서 공연을 관람하는 가격이다.

n개의 정수를 출력한다. 그중 i-th는 도시 i의 사람이 어떤 도시 j로 이동하고(또는 도시 i에 머물 수도 있다), 그곳에서 공연을 관람한 뒤 도시 i로 돌아오는 데 지출해야 하는 최소 코인 수 (if j ≠ i)와 같아야 한다.