#include using namespace std; typedef long long int ll; typedef pair P; typedef vector VI; typedef vector VVI; #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() constexpr ll MOD=1000000007; constexpr ll INF=1e18; struct E{ int to; ll l; ll a; int id; }; int n, m; int M=110000; vector> edge(M,vector(0)); vector lop(M,true); VI inc(M,0); VI ways(M,0); void dag(){ VI h(n,0); REP(i,n){ for(auto nx:edge[i]){ h[nx.to]++; } } queue q; REP(i,n){ if(h[i]==0){ q.push(i); } } while(!q.empty()){ int v=q.front(); lop[v]=0; q.pop(); for(auto nx:edge[v]){ if(--h[nx.to]==0){ q.push(nx.to); } } } } void initdfs(int v){ for(auto nx:edge[v]){ inc[nx.to]++; if(inc[nx.to]==1) initdfs(nx.to); } } void initdfs2(int v){ for(auto nx:edge[v]){ inc[nx.to]--; if(lop[v]) lop[nx.to]=1; if(inc[nx.to]==0) initdfs2(nx.to); } } VI ww(M,0), lp(M,0); void dfs(int v){ for(auto nx:edge[v]){ ww[nx.to]=(ww[nx.to]+ww[v]+lp[v]*nx.a%MOD*nx.l%MOD)%MOD; lp[nx.to]=(lp[nx.to]+lp[v]*nx.a)%MOD; if(--inc[nx.to]==0) dfs(nx.to); } } int main(){ cin >> n >> m; n++; int u, v, l, a; REP(i,m){ cin >> u >> v >> l >> a; edge[u].push_back(E{v,l,a,i}); } dag(); initdfs(0); initdfs2(0); if(lop[n-1]){ cout << "INF" << endl; return 0; } inc[0]++; initdfs(0); lp[0]=1; dfs(0); cout << ww[n-1] << endl; return 0; }