문제

수열 가 주어질 때, 에서 인접한 원소의 차가 모두 이라면 이러한 수열을 계단 수열이라고 합니다. 예를 들어, 과 은 계단 수열이지만, 나 는 계단 수열이 아닙니다.

정점 개, 양방향 간선 개로 구성된 그래프가 주어집니다. 그래프의 각 간선에는 이상 이하의 정수가 하나씩 적혀있습니다.

이 그래프의 정점 에서 하나 이상의 인접한 간선을 따라 이동하는 것을 반복하여 정점 에 도착했을 때, 통과한 간선에 적힌 정수를 나열한 수열이 계단 수열이라면 이를 정점 에서 정점 로 이동하는 계단 보행이라고 합니다. 이때 하나의 정점 또는 간선을 여러 번 사용할 수 있고, 하나의 간선을 여러 번 통과했다면 적힌 정수를 나열할 때에도 간선을 통과할 때마다 적어야 합니다. 이러한 계단 보행이 주어질 때, 그 길이는 이동 중 간선을 통과한 총 횟수로 정의합니다.

이때, 어떠한 보행이 계단 보행이 되기 위해서는 하나 이상의 인접한 간선을 따라 이동해야 함에 유의해야 합니다. 다시 말해, 정점 에서 간선을 따라 이동하지 않고 정점 에 남는 것은 정점 에서 정점 로 이동하는 계단 보행이 아닙니다.

인 각 정수 에 대해, 그래프의 번 정점에서 번 정점으로 이동하는 계단 보행이 존재하는지 알고자 합니다. 각 정점에 대해 그러한 계단 보행이 존재하는지 판단하고, 존재한다면 그중 가장 짧은 것의 길이를 출력해 주세요.

입력

첫 번째 줄에 정점의 개수 과 양방향 간선의 개수 이 공백으로 구분되어 주어집니다.

두 번째 줄부터 개의 줄에 각각 간선이 잇는 두 정점 , 와 간선에 적힌 숫자 가 공백으로 구분되어 주어집니다.

주어진 그래프에는 하나의 정점을 양끝으로 가지는 간선이 있거나 어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.

출력

총 개의 정수를 한 줄에 공백으로 구분하여 출력합니다. 각각의 값은 다음과 같습니다.

• 번 정점에서 번 정점으로 이동하는 계단 보행이 존재한다면, 번째로 출력되는 정수는 그러한 보행 중 가장 짧은 것의 거리입니다.
• 번 정점에서 번 정점으로 이동하는 계단 보행이 존재하지 않는다면, 번째로 출력되는 정수는 입니다.

제한

• 하나의 정점을 양끝으로 가지는 간선이 있을 수 있습니다.
• 어떤 두 정점을 연결하는 간선이 여러 개 있을 수 있습니다.

서브태스크

노트

예제에서 주어진 그래프는 다음과 같습니다.

각 정점에 대해 번 정점에서 해당 정점으로 이동하는 계단 보행은 다음과 같습니다.

• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점:
• 번 정점: 해당하는 계단 보행이 없습니다.

이때 번 정점에서 번 정점으로 이동하는 가장 짧은 계단 보행의 길이가 이 아님에 유의합니다.