자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.

자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다.

• 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다.
• 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고,
• 다른 모든 지점에서 1번 지점으로 갈 수 있다.

각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.

1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.

프로그램의 실행시간은 1초를 초과할 수 없다.

입력 형식

• 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다.
• 둘째 줄에는 도로의 개수 M이 주어진다.
• 이어 M 개의 줄에는 p q r 의 형식으로 도로의 정보가 주어지는데 이는

  p 번 지점부터 q 번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r 이라는 뜻이다.

출력 형식

• 첫째 줄에는 그 얻는 점수를 출력하고
• 둘째 줄에는 그 경로를 출력한다.

입출력 예

입력

8
13
1 2 5
1 3 4
2 5 2
2 6 1
3 6 3
5 6 7
5 8 9
6 8 3
4 1 6
6 4 8
7 4 5
6 7 2
8 7 4	

출력

32
1 2 5 6 8 7 4 1

출처:koi 지역