순환 버스의 가장 붐비는 구간

문제

한 순환 버스 노선에는 1번부터 N번까지 정류장이 있다. 버스는 1번, 2번, …, N번, 다시 1번 순서로 한 방향으로만 운행한다. 각 정류장에서 바로 다음 정류장까지 이동하는 부분을 구간이라고 부른다. 구간 번호는 출발 정류장의 번호와 같다. 따라서 N번 구간은 N번 정류장에서 1번 정류장으로 이동하는 부분이다. 노선 담당자는 여러 승객 묶음의 이동 계획을 받아, 모든 계획이 같은 운행에 적용될 때 가장 많은 승객이 타고 있는 구간을 찾으려고 한다. 이동 계획 하나는 승차 정류장 A, 하차 정류장 B, 함께 이동하는 승객 수 C로 이루어진다. 이 묶음의 승객 C명은 A번 정류장에서 타고, 운행 방향을 따라 이동하여 처음 만나는 B번 정류장에서 모두 내린다. A와 B는 항상 다르며, 어느 묶음도 한 바퀴 이상 이동하지 않는다. 어떤 묶음이 이용하는 구간에는 그 묶음의 승객 수를 더한다. 승차 정류장에서 출발하는 구간은 이용하지만, 하차 정류장에서 출발하는 구간은 이용하지 않는다. 예를 들어 정류장이 여섯 개일 때 5번에서 타서 2번에서 내리는 승객은 5번, 6번, 1번 구간을 이용한다. 2번에서 타서 5번에서 내리는 승객은 2번, 3번, 4번 구간을 이용한다. 각 이동 계획은 독립적인 승객 묶음을 뜻한다. 승차 정류장과 하차 정류장이 같은 계획이 여러 번 주어져도 모두 별도로 합산한다. 입력된 계획 이외의 승객은 없으며, 구간별 승객 수는 그 구간을 이용하는 모든 묶음의 승객 수를 더한 값이다. 이동 계획이 없으면 모든 구간의 승객 수는 0이다. 승객 수가 가장 많은 구간의 번호와 그 구간의 승객 수를 구하는 프로그램을 작성한다. 최대 승객 수가 같은 구간이 여러 개이면 구간 번호가 가장 작은 것을 선택한다. 버스의 수용 인원에는 제한이 없다고 가정한다.

입력

첫째 줄에 정류장 수 N과 이동 계획 수 M이 주어진다. 다음 M개 줄에 승차 정류장 A, 하차 정류장 B, 승객 수 C가 주어진다. 모든 값은 정수이며 2 ≤ N ≤ 100,000, 0 ≤ M ≤ 15,000, 1 ≤ A, B ≤ N, A ≠ B, 1 ≤ C ≤ 100이다.

출력

선택한 구간 번호와 해당 구간의 승객 수를 공백으로 구분하여 출력한다. 최대 승객 수가 같으면 가장 작은 구간 번호를 출력한다. M이 0이면 1 0을 출력한다.

6 3
5 2 4
1 4 3
3 6 2

1 7

5 2
2 4 6
4 2 6

1 6

3 0

1 0

출처: Devin.KR 자체 제작