#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 100 * 1000 + 7;
bool vis[N];
vector<pair<int, pair<ll, int>>> ed[N];
vector<ll> odl[N], sum[N];
vector<int>st[N];
map<int, int> col[N];
void Dijkstra()
{
int v, r; priority_queue<pair<ll, pair<int, int>>> q;
odl[1][0] = 0;
q.push(make_pair(0, make_pair(1, 0)));
while(q.size() > 0)
{
v = q.top().nd.st; r = q.top().nd.nd;
q.pop();
if(r > 0)
{
int co = col[v][r];
ll s = sum[v][co];
for(int i = st[v][co]; ed[v][i].st == r && i < (int)ed[v].size(); ++i)
{
ll o = odl[v][co] + s - ed[v][i].nd.st;
if(!vis[ed[v][i].nd.nd] && odl[ed[v][i].nd.nd][0] > o)
{
odl[ed[v][i].nd.nd][0] = o;
q.push(make_pair(-o, make_pair(ed[v][i].nd.nd, 0)));
}
}
continue;
}
if(vis[v]) continue;
vis[v] = true;
int curc = 0;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(i == 0 || ed[v][i].st != ed[v][i - 1].st) ++curc;
int ne = ed[v][i].nd.nd;
ll o = odl[v][0]; int co = col[ne][ed[v][i].st];
if(odl[ne][co] > o)
{
odl[ne][co] = o;
q.push(make_pair(-o, make_pair(ne, ed[v][i].st)));
}
o += ed[v][i].nd.st;
o = min(o, odl[v][0] + sum[v][curc] - ed[v][i].nd.st);
if(odl[ne][0] > o)
{
odl[ne][0] = o;
q.push(make_pair(-o, make_pair(ne, 0)));
}
}
}
}
void Solve()
{
int n, m, a, b, d, c;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> a >> b >> c >> d;
ed[a].pb(make_pair(c, make_pair(d, b)));
ed[b].pb(make_pair(c, make_pair(d, a)));
}
for(int i = 1; i <= n; ++i)
{
sort(ed[i].begin(), ed[i].end());
odl[i].pb(I); sum[i].pb(I); st[i].pb(-1);
for(int j = 0; j < (int)ed[i].size(); ++j)
{
if(j == 0 || ed[i][j].st != ed[i][j - 1].st)
{
odl[i].pb(I); sum[i].pb(0LL); st[i].pb(j);
col[i][ed[i][j].st] = st[i].size() - 1;
}
sum[i][sum[i].size() - 1] += ed[i][j].nd.st;
}
}
Dijkstra();
if(odl[n][0] == I)
cout << -1 << "\n";
else
cout << odl[n][0] << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
return 0;
}
