스카우트 탐험

당신은 스카우트 대장이고, 풀라우 우당에서 도보 탐험을 계획하고 있다. 지점은 $N (2 \leq N \leq 100)$개 있고, 두 지점 사이를 이동하는 데 걸리는 시간은 $100$ 이하의 양의 정수이며 모두에게 공개되어 있다.

지점에는 1번부터 $N$번까지 번호가 붙어 있다. 아래 그림은 $N = 8$인 예다.

모두 1번 지점에서 출발해 어떤 경로를 따라 $N$번 지점까지 가야 한다. 길이 갈라지는 지점에서 대원들은 동시에 나뉘어 갈라진 길로 각각 나아간다. 예를 들어 1번 지점에서는 두 무리로 나뉘어 한 무리는 5번 지점으로 가는 길을 탐험하고 다른 무리는 6번 지점으로 향한다. 5번 지점에 도착한 무리는 다시 둘로 나뉘어 하나는 2번 지점으로, 다른 하나는 3번 지점으로 간다. 즉 탐험하지 않고 남는 길은 없다. 대원마다 경로를 미리 정해 두어 필요한 수만큼 무리를 나눌 인원은 항상 충분하고, 이 경로 계획도 모두에게 공개되어 있다.

안전을 위해, 어떤 무리가 다른 무리보다 먼저 지점에 도착하면 나머지가 모두 안전하게 도착할 때까지 기다린 다음 다 함께 동시에 나뉘어 출발한다. 시각 0에 출발한다고 하자. 3번 지점에는 5번 지점을 거친 무리가 시각 9에 가장 먼저 도착하는데, 6번 지점과 4번 지점에서 오는 나머지 두 무리를 기다려야 한다. 세 무리가 모두 도착하면 두 무리로 나뉘어 2번 지점과 7번 지점으로 출발한다.

전체 출발 지점은 1번 하나뿐이고 전체 도착 지점은 $N$번 하나뿐이다. 모든 지점은 1번 지점에서 갈 수 있고, 모든 지점에서 $N$번 지점으로 갈 수 있다. 사이클이 있으면 같은 자리를 계속 맴돌게 되므로 사이클은 없다.

대원들이 시각 0에 출발할 때, 마지막 무리가 $N$번 지점에 도착하는 가장 이른 시각 $T$를 구해야 한다. 위 예에서는 $T = 35$다. 마지막 무리가 최종 지점인 8번에 도착하는 가장 이른 시각이 35라는 뜻이다.

먼저 도착한 무리는 나머지가 올 때까지 기다렸다가 다시 출발하므로 대기 시간이 생긴다. 한 지점의 대기 시간은 그 지점에 첫 무리가 도착한 시각과 마지막 무리가 도착한 시각의 차다. 예를 들어 3번 지점에는 첫 무리가 5번 지점을 거쳐 시각 9에 도착하고 마지막 무리가 6번 지점과 4번 지점을 거쳐 시각 14에 도착하므로, 3번 지점의 대기 시간은 5다. 같은 방식으로 2번 지점의 대기 시간은 13이다.

여행 전체의 총 대기 시간, 즉 모든 지점의 대기 시간을 더한 값도 구해야 한다. 위 예에서 총 대기 시간은 24다.

어떤 지점에서는 무리가 모두 도착한 뒤 곧바로 떠나지 않아도 된다. 쉬었다 출발해도 $N$번 지점에 시각 $T$보다 늦게 도착하지 않는다. 예를 들어 5번 지점에는 무리가 시각 5에 도착하지만, 마지막 무리가 8번 지점에 도착하는 가장 이른 시각 $T$를 늦추지 않으면서 시각 10까지 쉴 수 있다. 2번 지점에서도 무리가 모두 도착한 뒤 1만큼 더 쉴 수 있다. 나머지 지점에서는 지체 없이 바로 출발해야 한다. 따라서 이 예에서 출발을 미룰 수 있는 지점은 5번과 2번, 두 곳이다.

출발을 미룰 수 있는 지점이 몇 개인지도 구해야 한다.

첫째 줄에 지점의 수 $N (2 \leq N \leq 100)$과 길의 수 $M (1 \leq M \leq 1000)$이 주어진다. 다음 $M$개 줄에는 각각 정수 세 개가 주어지는데, 차례대로 길의 시작 지점, 끝 지점, 시작 지점에서 끝 지점까지 가는 데 걸리는 시간이다. 모든 값은 하나 이상의 공백으로 구분된다. 여행은 시각 0에 1번 지점에서 시작해 $N$번 지점에서 끝난다.

한 줄에 정수 세 개를 공백으로 구분해 출력한다. 차례대로 마지막 무리가 최종 지점 $N$번에 도착하는 가장 이른 시각 $T$, 총 대기 시간, 출발을 미룰 수 있는 지점의 수다.