페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5869
서브태스크

교차로 이동 로봇 2초 1024MB

문제

마을에는 N개의 교차로가 있으며 1에서 N까지 번호가 매겨져 있다. 또한 M개의 경로가 있으며 1에서 M까지의 번호가 붙어 있다.

각 도로는 두 개의 서로 다른 교차로를 양방향으로 연결한다. 도로 i (1≤i≤M)는 교차점 A_i와 교차점 B_i를 연결한다. 두 개의 다른 도로는 동일한 교차로 세트를 연결하지 않는다.

이 도로에는 1 이상 M 이하의 정수로 표현되는 색이 칠해져 있으며, 도로 i의 현재 색은 C_i이다. 여러 경로가 같은 색으로 칠해 질 수 있다.

지나는 마을의 교차로를 이동하는 로봇을 개발했다. 이 로봇에게 도로의 색을 지시하면 로봇은 지정된 색의 도로를 통과하여 인접한 교차로로 이동한다.

다만, 로봇이 현재 있는 교차로로 이어진 길 가운데, 지시된 색의 도로가 2개 이상 존재하면, 다음으로 진행할 길을 판별할 수 없게 되어 정지해 버린다.

당신의 목적은 현재 교차로 1에 있는 로봇에 지시를 여러 번 내려서 교차로 N으로 이동 시키는 것이다.

다만, 현재의 도로의 색으로는 그것이 불가능 할 수도 있기 때문에, 몇 개의 도로의 색을 바꾸는 것으로, 로봇을 교차점 N으로 이동 시킬 수 있는지 알고 싶다. 도로 i (1 ≤ i ≤ M)를 1 이상 M 이하의 좋아하는 정수의 색으로 바꾸기 위해서는 P_i원을 사용하여야 한다.

교차로와 도로 정보가 주어지면 필요한 금액의 최솟값을 찾는 프로그램을 작성하시오.

단, 도로의 색을 어떻게 바꾸어도 로봇을 교차로 N으로 이동 시킬 수 없는 경우에는 대신에 -1을 출력하라.


입력

입력은 다음 형식으로 표준 입력에서 제공된다. 입력 된 모든 값은 정수다.

N M

A_1 B_1 C_1 P_1

\vdots

A_M B_M C_M P_M

[제한]

• 2 ≤ N ≤ 100\, 000.

• 1 ≤ M ≤ 200 \,000.

• 1 ≤ A_i < B_i ≤ N (1 ≤ i ≤ M).

• (A_i, B_i) \neq (A_j, B_j) (1 ≤ i < j ≤ M).

• 1 ≤ C_i ≤ M (1 ≤ i ≤ M).

• 1 ≤ P_i ≤ 1 \,000 \,000 \,000 (1 ≤ i ≤ M).


출력

표준 출력에 필요한 금액의 최솟값을 한 줄로 출력하라.

단, 도로의 색을 어떻게 바꾸어도 로봇을 교차로 N로 이동시킬 수 없는 경우에는 대신에 -1을 출력하라.


부분문제

번호 점수 조건
#134점

N ≤ 1 000, M ≤ 2 000

#224점

P_i = 1 (1 ≤ i ≤ M)

#342점

추가 제약이 없다.


예제1

입력
46
1444
3413
1344
2431
2332
1242
출력
3

1 원으로 도로 4를 색 3에서 색 4로 바꾸고, 2 원으로 도로 6을 색 4에서 색 2로 바꾼다. (총 3원)

그 결과, 교차점 1에 있는 로봇에 색 2를 지시함으로써 로봇을 교차점 2로 이동 시킬 수 있다. 이어서 로봇에 색 4를 지시함으로써 로봇을 교차점 4로 이동 시킬 수 있다.

2 원 이하의 금액으로 로봇을 교차점 4로 이동 시키는 것은 불가능하기 때문에 3을 출력한다.


예제2

입력
52
1412
3514
출력
-1

예제3

입력
1321
71044
3647
81045
3925
1445
2642
31122
38162
811161
610414
68166
912165
51346
11247
24418
29410
21246
1013428
5725
511216
713420
출력
7

출처

JOI 2021

역링크