#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
#define ll long long
#define pb push_back
ll n, m, dist[N], dem[N], save[N], sum[N],a ,b ,c, p;
vector<array<ll,3>> adj[N];
priority_queue<array<ll,2>, vector<array<ll,2>>, greater<array<ll,2>> > pq;
bool vs[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> a >> b>> c >> p;
adj[a].pb({b,c,p});
adj[b].pb({a,c,p});
}
for (int i = 1; i <= n; i++)
{
dist[i]=1e18;
vs[i]=0;
}
dist[1]=0;
pq.push({0,1});
while(!pq.empty())
{
auto k = pq.top();
pq.pop();
if(vs[k[1]]) continue;
vs[k[1]]=1;
for (auto e : adj[k[1]])
{
sum[e[1]]=0;
dem[e[1]]=0;
save[e[1]]=1e18;
}
for (auto e : adj[k[1]])
{
sum[e[1]]+=e[2];
dem[e[1]]++;
save[e[1]]=min(save[e[1]], dist[e[0]]);
}
for (auto e : adj[k[1]])
{
if(dem[e[1]]==1)
{
if(dist[e[0]] > dist[k[1]])
{
dist[e[0]]=dist[k[1]];
pq.push({dist[e[0]], e[0]});
}
}
else
{
if(dist[e[0]] > dist[k[1]] + min(e[2], sum[e[1]] - e[2]))
{
dist[e[0]]=dist[k[1]] + min(e[2], sum[e[1]] - e[2]);
pq.push({dist[e[0]], e[0]});
}
}
if(dist[e[0]] > save[e[1]]+sum[e[1]] - e[2])
{
dist[e[0]]=save[e[1]]+sum[e[1]] - e[2];
pq.push({dist[e[0]], e[0]});
}
}
}
if(dist[n]==1e18) cout <<-1;
else cout << dist[n];
return 0;
}
