골목길

민승이는 집에서 출발해 목적지까지 가려고 한다. 두 장소 사이에는 여러 교차점과 일방통행 골목길이 복잡하게 이어져 있다.

각 골목길에는 정수 w가 붙어 있다. w가 양수이면 그 길을 지날 때 금품을 얻고, 음수이면 금품을 잃는다. 같은 길을 여러 번 지나면 그때마다 같은 금액을 얻거나 잃는다. 보유 금액은 음수가 될 수 있다.

교차점 1에서 출발해 교차점 n에 도착하는 경로 중 얻는 금액의 합이 최대인 경로를 출력해야 한다. 만약 금액을 한없이 크게 만들 수 있어 최적 경로가 존재하지 않으면 -1을 출력한다.

첫째 줄에 교차점의 개수 n (2 <= n <= 100)과 골목길의 개수 m (1 <= m <= 20,000)이 주어진다.

다음 m개 줄에는 세 정수 u, v, w가 주어진다. 이는 u번 교차점에서 v번 교차점으로 이동하는 일방통행 골목길이 있음을 뜻한다. w (0 <= |w| <= 1,000)는 그 길을 지날 때 얻거나 잃는 금액이다. 음수는 손실, 양수는 이득을 의미한다.

교차점 번호는 1 이상 n 이하이다. 출발지는 1번 교차점이고 도착지는 n번 교차점이다.

최적 경로가 존재한다면, 1번 교차점부터 n번 교차점까지 지나가는 교차점 번호를 공백으로 구분해 순서대로 출력한다.

최적 경로가 존재하지 않으면 -1을 출력한다. 최적 경로가 여러 개라면 아무거나 출력해도 된다.