#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(name)){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int maxn = 1e5+10;
const int INF = 1e9;
int n,m;
struct Edge{
int to, color, price, id;
};
vector<Edge> adj[maxn];
vector<pi> adj2[maxn];
int main(){
setIO();
cin>>n>>m;
vector<pair<pi, pi>> edges(m);
for (int i = 0; i < m; i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
a--; b--;
adj[a].pb({b, c, d, i});
adj[b].pb({a, c, d, i});
edges[i] = {{a,b}, {c,d}};
}
vi dist(n, INF);
dist[0] = 0;
priority_queue<pair<pi, pi>, vector<pair<pi, pi>>, greater<pair<pi, pi>>> pq;
pq.push({{0,0}, {-1,-1}});
while (!pq.empty()){
auto [cur, prev] = pq.top();
pq.pop();
auto [d, node] = cur;
auto [prevColor, prevId] = prev;
if (d > dist[node]) continue;
vi colors(m);
vi sum(m);
for (auto i : adj[node]){
if (i.id == prevId && prevColor == -1){
continue;
}
sum[i.color]+= i.price;
colors[i.color]++;
}
for (auto to : adj[node]){
int price = 0;
int color = to.color;
if (colors[to.color] > 1){
int changeAll = sum[to.color] - to.price;
if (changeAll > to.price){
color = -1;
}
price = min(changeAll, to.price);
}
if (dist[to.to] > d + price){
dist[to.to] = d + price;
pq.push({{dist[to.to], to.to}, {to.color, to.id}});
}
}
}
if (dist[n-1] == INF){
cout<<-1<<endl;
} else {
cout<<dist[n-1]<<endl;
}
}
