#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;
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;
void dijkstra(){
pq.emplace(0, mp(1, 0));
d[1][0] = 0;
while(!pq.empty()){
ll wu = pq.top().fi;
auto [u, c] = pq.top().se;
pq.pop();
if(wu != d[u][c] || vis[u][c]) continue;
// vis[u][c] = true;
// cout << u << " " << c << " " << wu << "?\n";
if(c){
for(pi ed: adj[u][c]){
if(d[ed.fi][0] > wu + (sum[u][c] - ed.se)){
d[ed.fi][0] = wu + (sum[u][c] - ed.se);
pq.emplace(d[ed.fi][0], mp(ed.fi, 0));
}
}
} else{
for(auto arr: adj[u]){
for(pi ed: arr.se){
ll tmp = wu + min(1LL * ed.se, sum[u][arr.fi] - ed.se);
if(!d[ed.fi].count(0) || d[ed.fi][0] > tmp){
d[ed.fi][0] = tmp;
pq.emplace(d[ed.fi][0], mp(ed.fi, 0));
}
if(!d[ed.se].count(arr.fi) || d[ed.fi][arr.fi] > wu){
d[ed.fi][arr.fi] = wu;
pq.emplace(d[ed.fi][arr.fi], mp(ed.fi, arr.fi));
}
}
}
}
}
}
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;
}
dijkstra();
if(d[n].count(0)) cout << d[n][0];
else cout << "-1";
return 0;
}
