前往大都会
题号：NC53303
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

题目译自 ROI 2017 Day 1 T4. Путешествие в Метрополис

某国有编号为1到n的n座城市，还有编号为1到m的m条铁路线。i号铁路线被沿途座城市分为s_i段。i号铁路线从起点到终点依次经过v[i,1],v[i,2],v[i,s]号城市，城市v[i,j]通过这条线路到城市v[i,j+1]花费的时间为t[i,j]。注意，本题中铁路线均为单向。
现在，你位于1号城市，你想要坐火车前往n号城市，途中可以换乘。你希望花费的时间最少，并且在花费时间最少的情况下使经过任意两个相邻城市所花费时间的平方和尽可能大，保证给你的图是一个连通图。

输入描述:

第一行，两个整数n,m，表示有n个城市，m条铁路线。
以下m行，每行描述一条铁路线：
开头一个整数s_i，之后个整数：v[i,1],t[i,1],v[i,2],t[i,2],v[i,3]。

输出描述:

一行，两个整数time,score，表示最少花费时间与最大的平方和。
示例1

输入

复制 
2 1
1 1 3 2

输出

复制 
3 9
示例2

输入

复制 
5 2
4 1 3 2 3 3 5 5 10 4
3 4 2 2 1 3 4 1

输出

复制 
9 35

说明

样例 2 如图所示。
从1号城市乘坐1号线直达5号城市并非最佳方案（无法达到最短时间）。
最佳方案：
从1号城市乘坐1号线到2号城市；
换乘2号线，坐到3号城市；
再换乘1号线，坐到5号城市。
此时，平方和为3^2+1^2+5^2=35。
示例3

输入

复制 
5 2
3 1 1 2 2 3 3 4
3 2 2 3 3 4 4 5

输出

复制 
10 82

说明

无论是在中途哪一站转2号线，结果都一样。平方和为1^2+9^2=82。

备注:

对于的数据，1⩽v[i,j]⩽n,1⩽t[i,j]⩽1000,。