#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const ll MOD=1e9+7; struct SCC{ vector> g, gr; int n, k; vector cmp, vs; vector used; void dfs(int x){ used[x]=1; for(auto y:g[x]){ if(!used[y]) dfs(y); } vs.push_back(x); } void rdfs(int v, int k){ used[v]=1; cmp[v]=k; for(auto y:gr[v]){ if(!used[y]) rdfs(y, k); } } SCC(const vector> &g):g(g), n(g.size()), cmp(n), used(n){ gr.resize(n); for(int x=0; x=0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } } }; int u[200010], v[200010]; ll l[200020], a[200020]; vector

g[200020]; int main() { int n, m; cin>>n>>m; vector> g0(n+1); for(int i=0; i>u[i]>>v[i]>>l[i]>>a[i]; g[u[i]].push_back({v[i], i}); g0[u[i]].push_back(v[i]); } SCC scc(g0); vector> w(scc.k); for(int i=0; i<=n; i++){ w[scc.cmp[i]].push_back(i); } bool dame[100010]={}; for(int i=0; i1){ for(auto x:w[i]) dame[x]=1; } } bool used[100010]={}; used[0]=1; queue que; que.push(0); while(!que.empty()){ int x=que.front(); que.pop(); for(auto q:g[x]){ int y=q.first; if(!used[y]){ que.push(y); used[y]=1; } } } if(!used[n]){ cout<<0<1) continue; int x=w[i][0]; for(auto q:g[x]){ int i=q.second; int y=q.first; if(dame[y]){ continue; } ok[y]=1; (dp[y]+=dp[x]*a[i])%=MOD; (dps[y]+=dps[x]*a[i]+dp[x]*l[i]%MOD*a[i])%=MOD; } } if(!ok[n]){ cout<<"INF"<