#include<bits/stdc++.h>
using namespace std;
#define DONTSYNC ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL) //dont use stdio with iostream functions //input and output are out of order now!
#define TEST unsigned long long T; cin>>T; while(T--)  //loop over each testcase
#define endl "\n"
#define fori(a,start,end) for(int a=start;a<end;a++)
#define forl(a,start,end) for(long long a=start;a<end;a++)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long     ll;
typedef long double   ld;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vii;
typedef vector<pll>   vll;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
const double PI = acos(-1);
ll calc_end_t(ll start,ll c,ll d){
    ll tmin=(ll)sqrt(d)-1;
    if(tmin<start) tmin=start;
    ll end=LLONG_MAX;
    for(ll i=tmin-2;i<tmin+3;i++){
        if(i==-1 || i<start) continue;
        end=min(end,i+c+d/(i+1));
    }
    return end;
}
void solve(){
    /* code */
    int n,m; cin>>n>>m;
    vector<vii> graph(n); vll edge(m);
    fori(i,0,m){
        int a,b,c,d; cin>>a>>b>>c>>d; a--;b--;
        graph[a].push_back({b,i});
        graph[b].push_back({a,i});
        edge[i]={c,d};
    }
    vl res(n,LLONG_MAX); res[0]=0;
    // priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({0,0});
    set<pll> pq; pq.insert({0,0});
    while(pq.size()){
        // auto [start_t,u]=pq.top(); pq.pop();
        auto [start_t,u]=*pq.begin(); pq.erase(pq.begin());
        if(start_t>res[u]) continue;
        for(auto [v,e]:graph[u]){
            ll end_t=calc_end_t(start_t,edge[e].fi,edge[e].se);
            if(end_t<res[v]){
                res[v]=end_t;
                // pq.push({end_t,v});
                pq.insert({end_t,v});
            }
        }
    }
    if(res[n-1]==LLONG_MAX) cout<<-1<<endl;
    else cout<<res[n-1]<<endl;
}

int main()
{
    DONTSYNC;
    // TEST
    solve();
    return 0;
}

/*
   Author   : MatsuTaku
   Date     : 01/09/21
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)         for (size_t i = 0, i##_len = (n); i < i##_len; i++)
using lint = long long int;
template<typename T>
using vvec = vector<vector<T>>;
template<typename T>
vvec<T> make_vvec(int n, int m, T v) { return vvec<T>(n, vector<T>(m, v)); }
template<typename T>
void chmax(T& dst, T x) { dst = max(dst, x); }
template<typename T>
void chmin(T& dst, T x) { dst = min(dst, x); }

class Solver {
 public:
  void solve();
};

constexpr int INF = 1e9;
void Solver::solve() {
  int n,m; cin>>n>>m;
  vector<tuple<int, int, int>> E(m);
  rep(i, m) {
    int a,b; cin>>a>>b; a--; b--;
    E[i] = {a, b, 0};
  }
  vector<int> C(n); for (auto& c:C) cin>>c;
  vector<int> Ci(n);
  iota(Ci.begin(), Ci.end(), 0);
  sort(Ci.begin(), Ci.end(), [&](auto l, auto r) {
    return C[l] > C[r];
  });
  vector<tuple<int, int, int>> H[n];
  rep(i, m) {
    auto& [a, b, id] = E[i];
    if (C[a] == C[b]) {
      H[a].emplace_back(b, i, H[b].size());
      H[b].emplace_back(a, i, H[a].size()-1);
    } else {
      id = C[a] > C[b] ? 1 : -1;
    }
  }
  vector<int> v(n);
  auto make_cycle = [&H, &E, &v](auto f, int s) -> void {
    if (v[s]) {
      return;
    }
    v[s] = true;
    for (auto& [t, ei, it] : H[s]) {
      auto& [es, et, eid] = E[ei];
      if (eid != 0) {
        continue;
      }
      eid = es == s ? 1 : -1;
      f(f, t);
    }
  };
  rep(i, n) {
    make_cycle(make_cycle, i);
  }
  for (auto [s, t, id] : E) {
    cout << (id == 1 ? "->" : "<-") << endl;
  }
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(10);
  Solver().solve();
  return 0;
}
