#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } #line 1 "Graph2/GraphTemplate.cpp" // graph template // ref : https://ei1333.github.io/library/graph/graph-template.cpp template struct Edge{ int from,to; T w; int idx; Edge()=default; Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){} operator int() const{return to;} }; template struct Graph{ vector>> g; int V,E; Graph()=default; Graph(int n):g(n),V(n),E(0){} size_t size(){ return g.size(); } void resize(int k){ g.resize(k); } inline const vector> &operator[](int k)const{ return (g.at(k)); } inline vector> &operator[](int k){ return (g.at(k)); } void add_directed_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E++); } void add_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E); g[to].emplace_back(to,from,cost,E++); } void read(int m,int pad=-1,bool weighted=false,bool directed=false){ for(int i=0;i>u>>v; u+=pad,v+=pad; T w=T(1); if(weighted) cin>>w; if(directed) add_directed_edge(u,v,w); else add_edge(u,v,w); } } }; #line 2 "Graph2/StronglyConnectedComponents.cpp" // scc.belong[i] : strongly connected components i belongs // scc.group[i] : vertice i-th strongly connected component has // scc.compressed : compressed Graph, DAG template struct StronglyConnectedComponents{ private: Graph g,rg; vector check; void dfs(int cur,vector &ord){ for(auto &to:g[cur])if(!check[to]){ check[to]=true; dfs(to,ord); } ord.push_back(cur); } void rdfs(int cur,int p){ for(auto &to:rg[cur])if(belong[to]==-1){ belong[to]=p; rdfs(to,p); } } public: vector belong; vector> group; Graph compressed; StronglyConnectedComponents(Graph &g):g(g),rg(g.size()),check(g.size()),belong(g.size(),-1){ for(int i=0;i<(int)g.size();i++)for(auto &e:g[i]) rg.add_directed_edge(e.to,e.from,e.w); build(); } // return compressed graph void build(){ vector ord; for(int i=0;i<(int)g.size();i++)if(!check[i]){ check[i]=true; dfs(i,ord); } int ptr=0;; for(int i=(int)ord.size()-1;i>=0;i--)if(belong[ord[i]]==-1){ belong[ord[i]]=ptr; rdfs(ord[i],ptr);ptr++; } compressed.resize(ptr); group.resize(ptr); for(int i=0;i<(int)g.size();i++){ int u=belong[i]; group[u].push_back(i); for(auto &e:g[i]){ int v=belong[e]; if(u!=v) compressed.add_directed_edge(u,v,e.w); } } return ; } }; template struct ModInt{ long long x; ModInt():x(0){} ModInt(long long y):x(y>=0?y%Mod:(Mod-(-y)%Mod)%Mod){} ModInt &operator+=(const ModInt &p){ if((x+=p.x)>=Mod) x-=Mod; return *this; } ModInt &operator-=(const ModInt &p){ if((x+=Mod-p.x)>=Mod)x-=Mod; return *this; } ModInt &operator*=(const ModInt &p){ x=(int)(1ll*x*p.x%Mod); return *this; } ModInt &operator/=(const ModInt &p){ (*this)*=p.inverse(); return *this; } ModInt operator-()const{return ModInt(-x);} ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;} ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;} ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;} ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;} bool operator==(const ModInt &p)const{return x==p.x;} bool operator!=(const ModInt &p)const{return x!=p.x;} ModInt inverse()const{ int a=x,b=Mod,u=1,v=0,t; while(b>0){ t=a/b; swap(a-=t*b,b);swap(u-=t*v,v); } return ModInt(u); } ModInt pow(long long n)const{ ModInt ret(1),mul(x); while(n>0){ if(n&1) ret*=mul; mul*=mul;n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const ModInt &p){return os<>(istream &is,ModInt &a){long long t;is>>t;a=ModInt(t);return (is);} static int get_mod(){return Mod;} }; using mint=ModInt<1000000007>; signed main(){ int n,m;cin>>n>>m;n++; Graph g(n); vector a(m); rep(i,m){ int u,v;mint w;cin>>u>>v>>w>>a[i]; g.add_directed_edge(u,v,w); } // INF? StronglyConnectedComponents scc(g); { vector check(scc.compressed.size(),true); for(int i=scc.belong[0];i<(int)scc.compressed.size();i++){ if(scc.group[i].size()>1) check[i]=false; if(!check[i])for(auto j:scc.compressed[i]) check[j]=false; } if(!check[scc.belong[n-1]]){ // assert(false); cout<<"INF"< dp(n,0); vector reach(n,false); reach[scc.belong[0]]=true; for(int i=scc.belong[0];i