메트로폴리스로 가는 여행

나라 안을 여행하는 일은 쉽지 않다. 특히 도시 사이에 직통 열차가 없을 때는 더 그렇다. 관광객 무리가 $1$부터 $n$까지 번호가 붙은 $n$개의 도시를 잇는 철도망을 이용해 메트로폴리스로 가려고 한다. 무리는 $1$번 도시에서 출발하고, 메트로폴리스는 $n$번 도시이다.

철도에서는 $m$개의 열차 노선이 운행 중이다. 각 노선은 열차가 지나는 도시를 순서대로 나열해 정해진다. 노선마다 인접한 두 도시 사이를 가는 데 걸리는 시간이 주어진다. 서로 다른 노선의 열차는 같은 구간을 서로 다른 시간에 지날 수 있다.

메트로폴리스로 가는 길에 무리는 노선 위의 어느 도시에서든 열차에 타고 내릴 수 있다. 첫 도시나 마지막 도시일 필요는 없다. 노선 $i$의 열차에서 내려 노선 $j$의 열차로 갈아탈 수 있고, 몇 번 더 갈아탄 뒤 다시 노선 $i$의 열차에 탈 수도 있다.

여행 방법은 두 기준으로 고른다. 첫째, 열차에서 보내는 총 시간이 최소여야 한다. 둘째, 최소 시간을 갖는 방법 중에서는 두 번의 갈아타기 사이에 끊기지 않고 열차에 타 있던 시간들의 제곱합이 최대인 방법을 고른다. 이 합을 여행의 질이라고 부른다.

열차 밖에서 보내는 시간은 계산하지 않는다. 노선 정보가 주어졌을 때, 열차 시간의 최솟값과 그 시간을 갖는 여행의 질의 최댓값을 구하는 프로그램을 작성하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \leq n \leq 10^6$, $1 \leq m \leq 10^6$). 각각 도시 수와 노선 수이다.

다음 $m$개의 줄에 노선이 하나씩 주어진다. 각 줄은 노선 $i$의 구간 수 $s_i$로 시작한다 ($1 \leq s_i \leq 10^6$). 이어서 $2s_i + 1$개의 정수가 $v_{i,1}, t_{i,1}, v_{i,2}, t_{i,2}, \ldots, t_{i,s_i}, v_{i,s_i+1}$ 순서로 주어진다. 여기서 $v_{i,j}$는 노선의 $j$번째 도시 번호이고, $t_{i,j}$는 $j$번째 도시와 $j+1$번째 도시 사이를 이동하는 데 걸리는 시간이다 ($1 \leq v_{i,j} \leq n$, $1 \leq t_{i,j} \leq 1000$).

모든 $s_i$의 합은 $10^6$을 넘지 않는다. 한 노선 안에서 같은 도시가 두 번 나오지 않는다. 주어진 노선으로 $1$번 도시에서 $n$번 도시까지 갈 수 있다.

두 정수를 출력한다. 첫 번째 정수는 열차에서 보내는 총 시간의 최솟값이고, 두 번째 정수는 그 시간을 갖는 방법 중 여행의 질의 최댓값이다.

두 번째 입력에서 1번 노선을 타고 1번 도시에서 곧장 가는 방법은 열차 시간이 최소가 되지 않으므로 최적이 아니다. 따라서 무리는 1번 노선으로 1번 도시에서 2번 도시까지 간 뒤, 2번 노선으로 2번 도시에서 3번 도시까지 가고, 다시 1번 노선으로 3번 도시에서 5번 도시까지 간다. 이때 타고 있던 시간의 제곱합은 $3^2 + 1^2 + 5^2 = 35$이다.

세 번째 입력에서는 2번, 3번, 4번 도시 중 어디에서 1번 노선에서 2번 노선으로 갈아타도 최소 시간이 나온다. 여행의 질이 최대가 되는 경우는 2번 도시에서 갈아탈 때이며, 그 값은 $1^2 + 9^2 = 82$이다.

두 번째와 세 번째 입력은 처음 두 부분문제의 제약을 만족하지 않는다. 솔루션은 첫 번째 샘플 입력을 통과해야 그 부분문제에서 채점된다. 샘플 입력은 3번부터 7번 부분문제의 제약을 만족하며, 모든 샘플을 통과해야 그 부분문제의 테스트에서 채점된다.