#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "QG04PAINT"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 1e5 + 1;
const ll INF = 1e18;
int n, m;
using pi = pair<int, int>;
map<int, vector<pi>> adj[N];
map<int, bool> vis[N];
map<int, ll> sum[N];
map<int, ll> d[N];
using node = pair<ll, pair<int, int>>;
priority_queue<node, vector<node>, greater<node>> pq;
ll dijkstra(const int &s, const int &e){
d[e][0] = INF;
pq.emplace(0, mp(s, 0));
d[s][0] = 0;
while(!pq.empty()){
ll wu = pq.top().fi;
auto [u, cu] = pq.top().se;
pq.pop();
if(wu != d[u][cu] || vis[u][cu]) continue;
vis[u][cu] = true;
// cout << u << " " << c << " " << wu << "?\n";
if(cu){
for(auto [v, wv]: adj[u][cu]){
ll tmp = wu + (sum[u][cu] - wv);
if(!d[v].count(0) || d[v][0] > tmp){
d[v][0] = tmp;
pq.emplace(tmp, mp(v, 0));
}
}
} else{
for(auto [cv, ed]: adj[u]){
for(auto [v, wv]: ed){
ll tmp = wu + min(1LL * wv, sum[u][cv] - wv);
if(!d[v].count(0) || d[v][0] > tmp){
d[v][0] = tmp;
pq.emplace(tmp, mp(v, 0));
}
if(!d[v].count(cv) || d[v][cv] > wu){
d[v][cv] = wu;
pq.emplace(d[v][cv], mp(v, cv));
}
}
}
}
}
return d[e][0] == INF ? -1 : d[e][0];
}
int main(){
IOS;
Fi();
cin >> n >> m;
FORU(i, 1, m){
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u][c].eb(v, p);
adj[v][c].eb(u, p);
sum[u][c] += p;
sum[v][c] += p;
}
cout << dijkstra(1, n);
return 0;
}
