#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct edge
{
int ver;
ll len;
edge(int _ver = 0, ll _len = 0)
{
ver = _ver;
len = _len;
}
bool operator < (const edge &e) const
{
return len > e.len;
}
};
const int maxn = 2e6 + 10;
int n, m, nxt;
map < pair < int, int >, int > mp;
map < pair < int, int >, ll > sum;
vector < edge > g[maxn];
int mp_idx(int v, int c)
{
if (mp.find(make_pair(v, c)) == mp.end())
mp[make_pair(v, c)] = ++ nxt;
return mp[make_pair(v, c)];
}
struct road
{
int v, u, c, p;
road(int _v = 0, int _u = 0, int _c = 0, int _p = 0)
{
v = _v;
u = _u;
c = _c;
p = _p;
}
}r[maxn];
const ll inf = 1e18;
ll d[maxn];
int used[maxn];
void add_edge(int v, edge e)
{
g[v].push_back(e);
///cout << v << " " << e.ver << " " << e.len << endl;
}
void solve()
{
cin >> n >> m;
nxt = n;
for (int i = 1; i <= m; i ++)
{
int v, u, c, p;
cin >> v >> u >> c >> p;
r[i] = road(v, u, c, p);
for (int t = 0; t < 2; t ++)
{
swap(v, u);
///g[v].push_back(edge(u, p));
add_edge(v, edge(u, p));
add_edge(v, edge(mp_idx(u, c), 0));
///g[v].push_back(edge(mp_idx(u, c), 0));
///cout << "to_add " << v << " " << c << " " << p << endl;
sum[make_pair(v, c)] += p;
}
}
map < pair < int, int >, int > :: iterator it;
for (int i = 1; i <= m; i ++)
{ int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
for (int t = 0; t < 2; t ++)
{
swap(v, u);
add_edge(v, edge(u, sum[make_pair(v, c)] - p));
add_edge(mp_idx(v, c), edge(u, sum[make_pair(v, c)] - p));
}
}
/**for (it = mp.begin(); it != mp.end(); it ++)
{
pair < int, int > cur = it -> first;
for (int j = 0; j < g[cur.first].size(); j ++)
{
int ver = g[cur.first][j].ver;
if (ver <= n)
{
///g[mp_idx(cur.first, cur.second)].push_back(edge(ver, sum[cur] - g[cur.first][j].len));
cout << cur.first << " :: " << cur.second << " :: " << sum[cur] << " " << g[cur.first][j].len << endl;
add_edge(mp_idx(cur.first, cur.second), edge(ver, sum[cur] - g[cur.first][j].len));
}
}
}*/
for (int i = 1; i <= m; i ++)
{
int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
for (int t = 0; t < 2; t ++)
{
swap(v, u);
if (sum[make_pair(v, c)] == p)
{
///g[v].push_back(edge(u, 0));
add_edge(v, edge(u, 0));
}
}
}
for (int i = 1; i <= nxt; i ++)
d[i] = inf;
priority_queue < edge > pq;
pq.push(edge(1, 0));
d[1] = 0;
while(!pq.empty())
{
edge e = pq.top();
pq.pop();
if (d[e.ver] >= e.len)
if (!used[e.ver])
{
used[e.ver] = 1;
for (int j = 0; j < g[e.ver].size(); j ++)
{
edge nb = g[e.ver][j];
nb.len += e.len;
if (nb.len < d[nb.ver])
{
d[nb.ver] = nb.len;
pq.push(nb);
}
}
}
}
if (d[n] == inf)
cout << -1 << endl;
else
cout << d[n] << endl;
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
///freopen("input.txt", "r", stdin);
speed();
solve();
return 0;
}
