1988. PG

【题目背景】

PG NOI2015 HA省队胡扯-第三场

LDN不知道为什么特别喜欢PG，也许是某种原因吧……

有一天，他发明了一个游戏“PG图”。

【题目描述】

给定一个有向图，每条边都有一个权值。

每次你可以选择一个节点$u$和一个整数$d$，把所有以$u$为终点的边的权值减小$d$，把所有以$u$为起点的边的权值加上$d$。最后要让所有边的权值的最小值为正且尽量大。

【输入格式】

输入包含若干组数据。

每组数据第一行为两个整数$n$和$m(n\leq500,m\leq2700)$，表示点和边的个数。

以下$m$行，每行包括$3$个整数$u,v,w$，表示$u\rightarrow v$有一条边权为$w$的边。$(1\leq u,v\leq n, -10000\leq w\leq 10000)$

【输出格式】

对于每组数据，输出边权最小值的最大值；

如果无法让所有边权都大于0，输出“No Solution”；

如果边权最小值可以无限大，输出“Infinite”。

【输入样例】

2 1
1 2 10
2 1
1 2 -10
3 3
1 2 4
2 3 2
3 1 5
4 5
2 3 4
4 2 5
3 4 2
3 1 0
1 2 -1

【输出样例】

Infinite
Infinite
3
1

【数据范围与约定】

对于30%的数据:$2\leq n\leq 10,1\leq m\leq 100$；

对于60%的数据:$2\leq n\leq 100,1\leq m\leq1000$；

对于100%的数据:$2\leq n\leq 500,1\leq m\leq2700$。