#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 1e5;
const int M = 2e5;
const ll INF = 3e18;
int n,m;
struct edge{
int u,v,c;
ll d;
}a[M+5];
struct edg1{
int v,c;
ll d;
};
vector<edg1> g[N+5];
ll dist[N+5];
ll cost[M+5],mi[M+5];
void dji(int x){
for(int i = 1 ; i <= n ; ++i) dist[i] = INF;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
dist[x] = 0;
pq.push({0,x});
while(!pq.empty()){
pair<ll,int> t = pq.top();
pq.pop();
ll w = t.fi;
int u = t.se;
if(dist[u] > w) continue;
for(edg1 i : g[u]){
mi[i.c] = INF;
cost[i.c] = 0;
}
for(edg1 i : g[u]){
mi[i.c] = min(mi[i.c],dist[i.v]);
cost[i.c] += i.d;
}
for(edg1 i : g[u]){
ll val = min(cost[i.c]-i.d,i.d);
if(dist[i.v] > w + val){
dist[i.v] = w + val;
pq.push({dist[i.v],i.v});
}
if(dist[i.v] > mi[i.c] + cost[i.c] - i.d){
dist[i.v] = mi[i.c] + cost[i.c] - i.d;
pq.push({dist[i.v],i.v});
}
}
}
if(dist[n] >= INF) cout << -1 << '\n';
else cout << dist[n];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i){
cin >> a[i].u >> a[i].v >> a[i].c >> a[i].d;
g[a[i].u].push_back({a[i].v,a[i].c,a[i].d});
g[a[i].v].push_back({a[i].u,a[i].c,a[i].d});
}
dji(1);
return 0;
}
