#include <bits/stdc++.h>
using namespace std;
#define taskname ""
#define ll long long
#define fi first
#define se second
#define pb push_back
const int N = 2e5+7;
ll n, m, dist[N],a,b,c,p;
vector<array<ll, 3>> adj[N];
map<ll,vector<array<ll,2>>> adj2[N];
map<ll,ll> dist2[N];
map<ll,ll> sum[N];
void mvu()
{
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});
adj2[a][c].pb({b,p});
adj2[b][c].pb({a,p});
sum[a][c]+=p;
sum[b][c]+=p;
}
for (int i = 2; i <= n; i++) dist[i]=1e18;
for (int i = 1; i <= n; i++)
{
for (auto j : adj[i])
{
dist2[i][j[1]]=1e18;
}
}
priority_queue<array<ll,3>, vector<array<ll,3>>, greater<>> pq;
pq.push({0,1,0});
while(!pq.empty())
{
auto k = pq.top();
pq.pop();
if(k[2]==0)
{
for (auto j : adj[k[1]])
{
if(k[0] > dist[j[0]]) continue;
if(dist[j[0]] > k[0]+sum[k[1]][j[1]]-j[2])
{
dist[j[0]]=k[0]+sum[k[1]][j[1]]-j[2];
pq.push({dist[j[0]], j[0], 0});
}
if(dist[j[0]] > k[0] + j[2])
{
dist[j[0]]=k[0]+j[2];
pq.push({dist[j[0]], j[0]});
}
if(dist2[j[0]][j[1]] > k[0])
{
dist2[j[0]][j[1]]=k[0];
pq.push({k[0], j[0], j[1]});
}
}
}
else
{
if(k[0] > dist2[k[1]][k[2]]) continue;
for (auto j : adj2[k[1]][k[2]])
{
if(dist[j[0]] > k[0] + sum[k[1]][k[2]] - j[1])
{
dist[j[0]] = k[0] + sum[k[1]][k[2]] - j[1];
pq.push({dist[j[0]], j[0], 0});
}
}
}
}
if(dist[n]==1e18) cout << -1;
else cout << dist[n];
}
int main()
{
if(fopen(taskname".inp", "r"))
{
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(false);
mvu();
return 0;
}
