자동차 경주

방향 그래프로 자동차 경주로가 주어진다. 각 정점은 지점이고, 각 방향 간선은 한쪽 방향으로만 이동할 수 있는 도로이다.

경주는 1번 지점에서 출발해 다시 1번 지점으로 돌아오는 코스이다. 단, 출발 후 도착하기 전까지는 1번 지점을 지나면 안 된다.

경주로는 다음 조건을 만족한다.

• 1번 지점을 제외한 어떤 지점에서도, 1번 지점을 지나지 않고 같은 지점으로 되돌아오는 경로는 없다.
• 1번 지점에서 모든 다른 지점으로 갈 수 있다.
• 모든 다른 지점에서 1번 지점으로 갈 수 있다.

각 도로에는 그 도로를 지날 때 얻는 점수가 있다. 1번 지점에서 출발해 다시 1번 지점으로 돌아오는 가능한 코스 중 총점이 가장 큰 코스의 점수와 경로를 출력하라.

첫째 줄에 지점의 개수 N이 주어진다. 각 지점은 1부터 N까지 번호가 매겨져 있다.

둘째 줄에 도로의 개수 M이 주어진다. 다음 M개의 줄에는 p q r이 주어진다. 이는 p번 지점에서 q번 지점으로 가는 일방통행 도로가 있고, 그 도로의 점수가 r이라는 뜻이다.

N은 1000 이하의 자연수이다. p와 q는 1 이상 N 이하의 자연수이고 서로 다르다. r은 100 이하의 자연수이다.

가장 높은 총점을 얻는 경로를 찾아 출력한다.

첫째 줄에 그 총점을 출력한다. 둘째 줄에 경로에서 지나는 지점 번호를 순서대로 출력한다. 번호 사이에는 공백을 하나씩 둔다.

출력 경로는 반드시 1번 지점에서 시작해 1번 지점에서 끝나야 한다. 최고 점수를 얻는 경로가 여러 개라면 그중 아무거나 하나만 출력하면 된다.