#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int inf = 1e18,N = 5e5+1,MOD = 998244353;
struct Edge {
int to,price,id;
};
void solve() {
int n,m;
cin >> n >> m;
unordered_map<int,vector<Edge>> edges[n+1];
unordered_map<int,int> sms[n+1];
vector<Edge> alledges[n+1];
vector<Edge> edg(m+1);
for (int i=1;i<=m;i++) {
int a,b,c,p;
cin >> a >> b >> c >> p;
edg[i] = {b,p,c};
edges[a][c].push_back({b,p,i});
edges[b][c].push_back({a,p,i});
alledges[a].push_back({b,p,i});
alledges[b].push_back({a,p,i});
sms[a][c]+=p;
sms[b][c]+=p;
}
vi dp(n+1,inf);
unordered_map<int,int> dpp[n+1];
for (int i=1;i<=n;i++) {
for (auto it : sms[i]) {
dpp[i][it.ff] = inf;
}
}
dp[1] = 0;
using State = pair<int,pair<int,pii>>;
priority_queue<State,vector<State>,greater<State>> pq;
pq.push({0,{0,{1,0}}});
while (!pq.empty()) {
auto[c,pr] = pq.top();
auto[typ,ppr] = pr;
auto[node,id] = ppr;
pq.pop();
if (typ == 0) {
if (dp[node] < c) continue;
for (Edge e : alledges[node]) {
if (dp[e.to] > c+sms[node][edg[e.id].id]-e.price) {
dp[e.to] = c+sms[node][edg[e.id].id]-e.price;
pq.push({dp[e.to],{0,{e.to,0}}});
}
if (dp[e.to] > c+e.price) {
dp[e.to] = c+e.price;
pq.push({dp[e.to],{0,{e.to,0}}});
}
if (dpp[e.to][edg[e.id].id] > c+e.price) {
dpp[e.to][edg[e.id].id] = c+e.price;
pq.push({dpp[e.to][edg[e.id].id],{1,{e.to,e.id}}});
}
}
}
else {
int col = edg[id].id;
int pri = edg[id].price;
if (dpp[node][col] < c) continue;
for (Edge e : edges[node][col]) {
if (e.id == id) continue;
if (dp[e.to] > c+sms[node][edg[e.id].id]-pri-e.price) {
dp[e.to] = c+sms[node][edg[e.id].id]-pri-e.price;
pq.push({dp[e.to],{0,{e.to,0}}});
}
if (dp[e.to] > c+e.price) {
dp[e.to] = c+e.price;
pq.push({dp[e.to],{0,{e.to,0}}});
}
if (dpp[e.to][edg[e.id].id] > c+e.price) {
dpp[e.to][edg[e.id].id] = c+e.price;
pq.push({dpp[e.to][edg[e.id].id],{1,{e.to,e.id}}});
}
}
}
}
int ans = dp[n];
for (auto it : dpp[n]) ans = min(ans,it.ss);
if (ans >= inf) cout << -1 << '\n';
else cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
