#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;
vector <vector <pll> > g(nmax);
ll d[nmax];
vector <bool> used(nmax);
map <pii, int> mp;
int cnt = 0;
vector <vector <pair<pii, int> > >G(200001);
int m;
void process(vector <pii> cur, int v){
ll s = 0;
vector <int> vv;
for(auto to : cur){
mp[{v, to.s}] = cnt;
vv.pb(cnt++);
vv.pb(cnt++);
s += (ll)to.f;
}
for(int j = 0; j < cur.size(); j++){
int x = vv[j * 2], y = vv[j * 2 + 1];
g[4 * m + v].pb({y, cur[j].f});
g[4 * m + v].pb({x, s - (ll)cur[j].f});
g[x].pb({4 * m + cur[j].s, 0});
g[y].pb({4 * m + cur[j].s, 0});
}
}
void process1(vector <pii> cur, int v){
ll s = 0;
for(int i = 0; i < cur.size(); i++){
s += (ll)cur[i].f;
}
for(int i = 0; i < cur.size(); i++){
int x = mp[{cur[i].s, v}];
x++;
if(i == cur.size() - 1){
if(cur.size() == 1) continue;
int o = cur[cur.size() - 2].s;
int y = mp[{v, o}];
g[x].pb({y, s - (ll)cur[i].f - (ll)cur[i - 1].f});
}
else{
int y = cur.back().s;
y = mp[{v, y}];
g[x].pb({y, s - (ll)cur[i].f - cur.back().f});
}
}
}
int main(){
int n; cin >> n;
cin >> m;
for(int i = 1; i <= m; i++){
int u, v, c, p; cin >> u >> v >> c >> p;
G[u].pb({{c, p}, v});
G[v].pb({{c, p}, u});
}
for(int v = 1; v <= n; v++){
if(G[v].empty()) continue;
sort(G[v].begin(), G[v].end());
vector <pii> cur;
cur.epb(G[v][0].f.s, G[v][0].s);
for(int i = 1; i < G[v].size(); i++){
if(G[v][i].f.f == G[v][i - 1].f.f){
cur.epb(G[v][i].f.s, G[v][i].s);
}
else{
process(cur, v);
cur.clear();
cur.epb(G[v][i].f.s, G[v][i].s);
}
}
process(cur, v);
}
for(int v = 1; v <= n; v++){
if(G[v].empty()) continue;
sort(G[v].begin(), G[v].end());
vector <pii> cur;
cur.epb(G[v][0].f.s, G[v][0].s);
for(int i = 1; i < G[v].size(); i++){
if(G[v][i].f.f == G[v][i - 1].f.f){
cur.epb(G[v][i].f.s, G[v][i].s);
}
else{
process1(cur, v);
cur.clear();
cur.epb(G[v][i].f.s, G[v][i].s);
}
}
process1(cur, v);
}
for(int i = 0; i <= 4 * m + n; i++){
d[i] = 1e18;
}
d[4 * m + 1] = 0;
priority_queue<pll> q;
q.push({0, 4 * m + 1});
while(!q.empty()){
int v = q.top().s;
q.pop();
if(used[v]) continue;
used[v] = true;
for(auto ed : g[v]){
int to = ed.f;
ll len = ed.s;
if(d[to] > d[v] + len){
d[to] = d[v] + len;
q.push({-d[to], to});
}
}
}
if(d[4 * m + n] == 1e18)
cout << -1;
else
cout << d[4 * m + n];
return 0;
}
