题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。

这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。

在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。

你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入格式

• 第$\red 1$行: 两个整数$\red{N(2<=N<=32)}$、$\red{M(0<=M<=1000)}$, $\red N$表示仓库的数目，$\red M$表示运输卡车的数量。仓库$\red 1$代 表发货工厂，仓库$\red N$代表有三聚氰胺的牛奶要发往的零售商。
• 第$\red{2\sim M+1}$行: 每行$\red 3$个整数$\red{S_i}$,$\red{E_i}$,$\red{C_i}$。其中$\red{S_i}$,$\red{E_i}$表示这 辆卡车的出发仓库，目的仓库。$\red{C_i(0 <= C_i <= 2,000,000)}$ 表示让这辆卡车停止运输的损失。

输出格式

请输出相两个整数$\red C$、$\red T$：$\red C$表示最小的损失，$\red T$表示在损失最小的前提下，最少要停止的卡车数。

应的表达式$\red{S_n}$，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例

输入样例

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

输出样例

60 1