#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 3e5 + 1;
ll t[4 * N], arr[N];
void build(ll v, ll tl, ll tr){
    if(tl == tr){
        t[v] = arr[tl];
        return;
    }
    ll tm = (tl + tr) /2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = t[2 * v] ^ t[2 * v + 1];
}
void update(ll v, ll tl, ll tr, ll idx, ll y){
    if(tl == tr){
        t[v] ^= y;
        return;
    }
    ll tm = (tl + tr) / 2;
    if(idx <= tm){
        update(2 * v, tl, tm, idx, y);
    }
    else{
        update(2 * v + 1, tm + 1, tr, idx, y);
    }
    t[v] = t[2 * v] ^ t[2 * v + 1];
} 
ll query(ll v, ll tl, ll tr, ll l, ll r){
    if(l > r){
        return 0;
    }
    if(tl == l && tr == r){
        return t[v];
    }
    ll tm = (tl + tr) / 2;
    ll lef, rig;
    lef = query(2 * v, tl, tm, l, min(r, tm));
    rig = query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    return (lef ^ rig);
}
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        ll n, q;
        cin >> n >> q;
        for(i = 1; i <= n; i++){
            cin >> arr[i];
        }
        build(1, 1, n);
        while(q--){
            ll t;
            cin >> t;
            ll x, y;
            cin >> x >> y;
            if(t == 1){
                update(1, 1, n, x, y);
            }
            else{
                cout << query(1, 1, n, x, y) << "\n";
            }
        }
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define pb push_back
#define endl '\n'
#define sa(x) sort((x).begin(), (x).end());
#define int long long

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T> static inline void sd(vector<T> &x) {sort((x).begin(), (x).end(), greater<T>()) ; }

int n, m;
const int N=1e5+5;
vector<pair<int, pair<int, int>>> g[N];
#define ii pair<ll, ll>
#define vii vector<ii>
#define x first
#define y second
const int inf=LLONG_MAX;
void solve(){
	cin>>n>>m;
    rep(i,0,m)
    {
        int e, f, c, d;
        cin>>e>>f>>c>>d;
        g[e].pb({f, {c, d}});
        g[f].pb({e, {c, d}});
    }

    set<ii> se;
    se.insert({0, 1});
    vi dis(n+1, inf);
    while(!se.empty())
    {
        auto top = *(se.begin());
        se.erase(se.begin());

        int v=top.y;
        dis[v] = top.x;
        for(auto ch : g[v])
        {
            int D=ch.y.y, X=dis[v], C=ch.y.x, tar=ch.x;
            // cout<<v<<" to "<<tar<<endl;
            // cout<<C<<" and "<<D<<" "<<X<<endl;
            int t = sqrt(D) - X - 1;
            vector<int> ts = {max(t-1, 0ll), max(t, 0ll), max(t+1, 0ll)};

            int ans=dis[tar];

            for(int tt : ts)
            {
                // cout<<tt<<" "<<1<<" "<<X<<endl;
                int tmp = C + D/(tt+1+X) + X + tt;
                // cout<<"wait "<<tt<<" get"<<tmp<<endl;
                if(tmp < ans)
                {
                    ans=tmp;
                }
            }

            if(ans < dis[tar])
            {
                if(dis[tar] != inf)
                {
                    se.erase({dis[tar], tar});
                }
                dis[tar] = ans;
                se.insert({dis[tar], tar});
            }

        }
    }

    // rep(i, 1, n+1)
    // {
    //     if(dis[i]!=inf) cout<<dis[i]<<" ";
    //     else cout<<"x ";
    // }

    if(dis[n] != inf)
        cout<<dis[n];
    else cout<<-1;
}

signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int testcases=1;
	//cin>>testcases;
	while(testcases--){
		solve();
	}
	return 0;	
}
