[SDOI2009]晨跑

Elaxia 最近迷上了空手道，并为自己制订了一套包括俯卧撑、仰卧起坐等项目的健身计划。不过，到目前为止，他唯一坚持下来的项目是晨跑。

学校附近有 $N$ 个路口和 $M$ 条单向街道。每条街道连接两个路口，街道之间只在路口处相交。Elaxia 每天从编号为 $1$ 的寝室出发，沿街道跑到编号为 $N$ 的学校。

Elaxia 的晨跑计划按周期进行，每个周期包含若干天。由于他不喜欢重复的路线，同一周期内任意两天的晨跑路线不能经过相同的路口，但寝室和学校除外。

Elaxia 希望训练周期包含的天数尽可能多；在此基础上，他还希望一个周期内晨跑的总路程尽可能短。请你为他设计一套满足要求的晨跑计划。

输入格式

第一行包含两个整数 $N,M$，分别表示路口数和街道数。

接下来 $M$ 行，每行包含三个整数 $a,b,c$，表示存在一条从路口 $a$ 到路口 $b$、长度为 $c$ 的单向街道。

输出格式

输出两个整数。第一个整数表示最长训练周期的天数，第二个整数表示在周期天数最长的前提下，一个周期内晨跑的最短总路程。

样例输入

7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1

样例输出

2 11

数据范围

• $N\le 200$；
• $M\le 2\times 10^4$。

来源与许可

本题为 SDOI 2009 试题「晨跑」，题面与测试数据整理自 BZOJ。

样例 1

输入

7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1

输出

2 11