405014 - 路径统计

地图上有N个结点和E条道路,所有道路都是单向的,问从结点1到结点N的最短路径有多少条?

输入

输入第一行为两整数N和E,表示结点和道路数。 随后E行,每行三个数x、y、c,表示从结点x到结点y有道路相连且花费时间为c(可能有重复输入的边,但保证x≠y,1≤x,y≤n)。

输出

输出两个数,分别是最少花费时间和花费时间最少的路径数。 两个不同的最短路方案要求:路径长度相同(均为最短路长度)且至少有一条边不重合。 若城市N无法到达则输出“No answer”。

样例

输入

5 5
1 2 1
2 3 1
3 4 1
1 4 3
4 5 2

输出

5 2

提示

对于30%的数据:N≤20; 对于100%的数据:1≤N≤2 000,0≤E≤N×(N-1),1≤c≤10。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题