2630: 最小奖励

Jzabc更是一个狂热的旅游爱好者。这次他想去一个诡异的地方。这个地方有n个村庄，编号为1到n。此刻他在1号村庄，他想去n号村庄。这n个村庄之间有m条单向道路。通过某些道路时，可能会花费一些钱作为“买路钱”，可是通过一些道路时，不仅不需要交“买路钱”，而且会得到一些奖励（这就是诡异的地方？）。当然两个村庄之间可能有多条直接相连的道路。但是每一条路只能通过一次。

这些村庄有这样的特性，从任何一个村庄出发，沿着任一条路径走都不会回到出发点。找到一条路径从1号村庄到n号村庄后，他需要计算一共得到多少奖励，一共交了多少“买路钱”。如果得到的总奖励钱数大于交的“买路钱”数，那么称这走一条路径可以得到奖励；相反，如果前者小于后者，那么称走这一条路径需要花费。如果两者相等，那么Jzabc不会选这一条路（我也不知道他为什么不选这一条路径）。不会出现所有的路径两者都相等。他又需要你的帮助，让你找一条路径，使他得到的奖励最小（为什么不是最大的奖励？），并输出最小奖励。如果找不到一条路径能使他得到奖励，那么就找一条路径是他得到的花费最大（为什么就不是最小的花费？），并输出最大花费。

第一行

两个正整数n，m，中间用空格隔开

n是村庄总数，m是道路总数

以下m行，每行三个正整数x，y，w，描述一条道路的信息，中间用空格隔开

x是此条道路的起点，y是终点，

若w为正，则是通过此条道路得到的奖励钱数

若w为负，则是通过此条道路交的“买路钱”数

w不为0，并且|w|<=10；

一个整数。若有最小奖励，则输出。否则输出最小花费。

3 4
1 2 2
2 3 -1
2 3 3
1 3 -1

1