#include<bits/stdc++.h>
using namespace std;
const int N=22;
const int M=110;
#define pii pair<int,int>
using ll=long long;
#define mp make_pair
#define mid (l+r>>1)

vector<vector<int> > v(N);
vector<int> status(1<<N,0);

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

//vector<int> f(N,1);
//
//void init(){
//    for(int i=1;i<N;i++) f[i]=f[i-1]<<2;
//}
int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;i++){
        int a=read()-1,b=read()-1;
        v[a].push_back(b);
        v[b].push_back(a);
        for(int j=0;j<(1<<n);j++) if((j>>a&1)&&(j>>b&1)) status[j]=-1;
    }
    ll ans=0;
    for(int i=0;i<(1<<n);i++){
        if(status[i]==-1) continue;
        vector<int> color(N,-1);
        for(int j=0;j<n;j++) if(i>>j&1) color[j]=2;
        queue<int> q;
        int num=0;
        bool ok=false;
        for(int j=0;j<n;j++){
            if(color[j]!=-1) continue;
            q.push(j);
//            cout<<i<<" "<<j<<"\n";
            color[j]=0;
            num++;
            while(q.size()){
                int x=q.front();
                q.pop();
                for(auto y:v[x]){
                    if(color[x]==color[y]){
                        ok=true;
                        break;
                    }
//                    cout<<x<<" "<<y<<"\n";
                    if(color[y]==-1){
                        color[y]=color[x]^1;
                        q.push(y);

                    }
                }
                if(ok) break;
            }
            if(ok) break;
        }
//        cout<<i<<" "<<num<<"\n";
        if(!ok) ans+=1<<num;
    }
    printf("%lld\n",ans);
}



#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define setbits(n) __builtin_popcountll(n)
#define mkunique(a) sort(a.begin(),a.end()); a.resize(unique(a.begin(),a.end())-a.begin());
#define print(s) for(ll u: s) cout<<u<<" "; cout<<"\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
 
const int N=1e5+10;
vector<pair<ll,pair<ll,ll>>> a[N];
 
int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll TT=clock();
 
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v,c,d;
        cin>>u>>v>>c>>d; u--,v--;
        a[u].pb({v,{c,d}});
        a[v].pb({u,{c,d}});
    }
    vector<ll> d(n,mod*mod);
    d[0] = 0;
    set<pair<ll,ll>> s;
    s.insert({0,0});
    while(!s.empty()){
        ll v = s.begin()->ss;
        s.erase(s.begin());
        for(auto ed: a[v]){
            ll u = ed.ff, c = ed.ss.ff, dd = ed.ss.ss;
            ll t = d[v];
            ll wait = max(0ll,(ll)sqrt(dd) - 1ll - t);
            for(ll i=max(0ll,wait-1);i<=wait+1;i++){
                ll cost = t + i + c + dd/(t+i+1);
                if(cost < d[u]){
                    s.erase({d[u],u});
                    d[u] = cost;
                    s.insert({d[u],u});
                }
            }
        }
    }
    if(d[n-1]==mod*mod)
        cout<<-1;
    else
        cout<<d[n-1];
 
 
    cerr<<"\n\nTIME: "<<(long double)(clock()-TT)/CLOCKS_PER_SEC<<" sec\n";
    TT = clock();
    return 0;
}