#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
const int N = 1e5 + 5;
int n, m;
#define tup tuple<int, int, int>
vector<tup> adj[N];
vector<ll> dist[N][2];
ll cost[N];
vector<int> match[N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "robot1"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int u, v, c, p; cin>>u>>v>>c>>p;
adj[u].emplace_back(v, c, p);
adj[v].emplace_back(u, c, p);
match[u].push_back(adj[v].size() - 1);
match[v].push_back(adj[u].size() - 1);
}
if (n == 1) return cout<<0, 0;
if (adj[1].empty()) return cout<<-1, 0;
dist[1][0].resize(adj[1].size(), 0);
dist[1][1].resize(adj[1].size(), 0);
for (int i = 2; i <= n; i++)
for (int t = 0; t <= 1; t++)
dist[i][t].resize(adj[i].size(), 1e16);
// dist u t from
#define Tup tuple<ll, int, int, int>
priority_queue<Tup, vector<Tup>, greater<Tup>> pq;
pq.push({0, 1, 0, 0});
while (!pq.empty()) {
auto [d, u, t, from] = pq.top();
pq.pop();
if (d != dist[u][t][from])
continue;
if (u == n) return cout<<d, 0;
int m = adj[u].size();
for (int i = 0; i < m; i++) {
auto [v, c, p] = adj[u][i];
cost[c] = 0;
}
for (int i = 0; i < m; i++) {
if (t == 1 && i == from)
continue;
auto [v, c, p] = adj[u][i];
cost[c] += p;
}
//cout<<u<<'\n';
for (int i = 0; i < m; i++) {
if (t == 1 && i == from)
continue;
auto [v, c, p] = adj[u][i];
ll Cost = cost[c] - p;
if (dist[v][0][match[u][i]] > d + Cost) {
dist[v][0][match[u][i]] = d + Cost;
pq.push({d + Cost, v, 0, match[u][i]});
//cout<<v<<' '<<u<<' '<<0<<' '<<d + Cost<<'\n';
}
Cost = p;
if (dist[v][1][match[u][i]] > d + Cost) {
dist[v][1][match[u][i]] = d + Cost;
pq.push({d + Cost, v, 1, match[u][i]});
//cout<<v<<' '<<u<<' '<<1<<' '<<d + Cost<<'\n';
}
}
}
cout<<-1;
cerr<<setprecision(3)<<fixed<<"Time elapsed: "<< 1.0 * clock() / CLOCKS_PER_SEC <<"s\n";
}
