#include #define rep(i,n) for(int i=0;i<(int)(n);i++) #define chmin(x,y) x = min((x),(y)); #define chmax(x,y) x = max((x),(y)); using namespace std; using ll = long long ; using P = pair ; using pll = pair; const int INF = 1e9; const long long LINF = 1e17; const int MOD = 1000000007; //const int MOD = 998244353; const double PI = 3.14159265358979323846; template struct ModInt{ long long x=0; constexpr ModInt(long long x=0):x((x%mod+mod)%mod){} constexpr ModInt operator+(const ModInt& r)const{return ModInt(*this)+=r;} constexpr ModInt operator-(const ModInt& r)const{return ModInt(*this)-=r;} constexpr ModInt operator*(const ModInt& r)const{return ModInt(*this)*=r;} constexpr ModInt operator/(const ModInt& r)const{return ModInt(*this)/=r;} constexpr ModInt& operator+=(const ModInt& r){ if((x+=r.x)>=mod) x-=mod; return *this;} constexpr ModInt& operator-=(const ModInt& r){ if((x-=r.x)<0) x+=mod; return *this;} constexpr ModInt& operator*=(const ModInt& r){ if((x*=r.x)>=mod) x%=mod; return *this;} constexpr ModInt& operator/=(const ModInt& r){ return *this*=r.inv();} ModInt inv() const { long long s=x,sx=1,sy=0,t=mod,tx=0,ty=1; while(s%t!=0){ long long temp=s/t,u=s-t*temp,ux=sx-temp*tx,uy=sy-temp*ty; s=t;sx=tx;sy=ty; t=u;tx=ux;ty=uy; } return ModInt(tx); } ModInt pow(long long n) const { ModInt a=1; ModInt b=*this; while(n>0){ if(n&1) a*=b; b*=b; n>>=1; } return a; } friend constexpr ostream& operator<<(ostream& os,const ModInt& a) {return os << a.x;} friend constexpr istream& operator>>(istream& is,ModInt& a) {return is >> a.x;} }; using mint = ModInt; vector ToplogicalSort(vector> &G,vector &Indegree){ int n = (int)G.size(); vector res(n); queue q; for(int i=0;i> n >> m; vector> G(n+1); vector> graph(n+1); vector Indegree(n+1,0); rep(i,m){ ll u,v,l,a; cin >> u >> v >> l >> a; G[u].push_back(v); graph[u].push_back(edge{v,l,a}); Indegree[v]++; } int n_ = 0; map temp_real; map real_temp; auto dfs = [&](auto&& dfs,int i) -> bool{ if(seen[i]==1) return false; bool res = false; if(i == n) res = true; seen[i] = 1; for(int j:G[i]){ if(seen[j]) continue; bool temp = dfs(dfs,j); if(temp) res = true; } if(res){ temp_real[n_] = i; real_temp[i] = n_; ++n_; } return res; }; dfs(dfs,0); vector Indegree_(n_,0); vector> G_(n_); rep(i,n+1){ if(real_temp.count(i) == 0) continue; int idx = real_temp[i]; for(int j:G[i]){ if(real_temp.count(j) > 0){ G_[idx].push_back(real_temp[j]); Indegree_[real_temp[j]] ++; } } } if(real_temp.count(n) == 0){ cout << 0 << endl; return 0; } vector top = ToplogicalSort(G_,Indegree_); if(top[0]==-1){ cout << "INF" << endl; return 0; } vector topo(n_); rep(i,n_){ topo[i] = temp_real[top[i]]; } dp[0] = 0; cnt[0] = 1; for(int i:topo){ for(auto e:graph[i]){ dp[e.to] += dp[i] * e.a + cnt[i] * e.a * e.l; cnt[e.to] += cnt[i] * e.a; } } cout << dp[n] << endl; return 0; }