记录编号	185917	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	PG	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	17.280 s
提交时间	2015-09-10 13:11:19	内存使用	0.39 MiB

/*
Problem:PG;
Language:c++;
by dydxh;
Date:2015.09.10;
*/
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<queue>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn=505;
const int maxm=2705;
const int oo=2000000000;
int n,m,ans,len;
int linkk[maxn];
struct edge{
	int y,next,v;
}e[maxn+maxm];
struct edger
{
	int u,v,w;
}eg[maxm];
inline int read(){
	int x=0;bool flag=0;char ch=getchar();
	while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
void insert(int a,int b,int c){
	e[++len].next=linkk[a];
	linkk[a]=len;
	e[len].y=b;
	e[len].v=c;
}	
void Build_Graph(){
	len=0;
	memset(linkk,0,sizeof(linkk));
	for(int i=1;i<=m;i++)
		insert(eg[i].v,eg[i].u,-eg[i].w);
	for(int i=1;i<=n;i++)
		insert(0,i,0);
}
int q[maxn+6],Dis[maxn],vis[maxn];
bool flag[maxn];
int head,tail;
bool SPFA(int x){
	memset(flag,0,sizeof(flag));
	memset(Dis,-1,sizeof(Dis));
	memset(vis,0,sizeof(vis));
	head=0,tail=1,q[1]=0,Dis[0]=0,vis[0]=1;
	while(head!=tail){
		head++;if(head>maxn) head=1;
		int tn=q[head];flag[tn]=0;
		for(int i=linkk[tn];i;i=e[i].next){
			int tmp=e[i].y;
			if(Dis[tmp]<Dis[tn]+x+e[i].v){
				Dis[tmp]=Dis[tn]+x+e[i].v;
				if(!flag[tmp]){
					tail++;if(tail>maxn) tail=1;
					flag[tmp]=1,q[tail]=tmp;
					vis[tmp]++;
					if(vis[tmp]>n) return 0;
				}
			}
		}
	}
	return 1;
}
void dydxh_sol(){
	int leftt=0,rightt=10002;
	ans=-1;
	while(leftt+1<rightt){
		int mid=(leftt+rightt)>>1;
		if(SPFA(mid)) leftt=ans=mid;
		else rightt=mid;
	}
	if(ans==-1) printf("No Solution ");
	else if(rightt==10002) printf("Infinite ");
	else printf("%d ",ans);
}
int main(){
	//srand(time(0));
	freopen("PG.in","r",stdin);
	freopen("PG.out","w",stdout);
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=1;i<=m;i++)
			eg[i].u=read(),eg[i].v=read(),eg[i].w=read();
		Build_Graph();
		dydxh_sol();
	}
	printf("\n");
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
	return 0;
}