#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int MAXX = 5e5 + 5;
const int INF = 1e18;
struct edge
{
int u, v, c, w;
};
int n, m;
int id;
map<pii,int> mp;
vector<pii> adj[MAXX];
vector<edge> peal;
int sum[MAXX];
int d[MAXX];
int get(int a, int c)
{
if (mp.find({a, c}) == mp.end())
{
mp[{a, c}] = ++id;
}
return mp[{a,c}];
}
void dijkstra()
{
for (int i = 1; i <= n + 2 * m; i++)
{
d[i] = INF;
}
d[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({d[1], 1});
while(!pq.empty())
{
auto [dist, u] = pq.top();
pq.pop();
if (dist > d[u])
{
continue;
}
for (auto[v, w] : adj[u])
{
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
id = n;
for (int i = 1; i <= m; i++)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
peal.push_back({u, v, c, w});
int curu = get(u, c);
sum[curu] += w;
int curv = get(v, c);
sum[curv] += w;
}
for (auto[u, v, c, w] : peal)
{
for (int t = 0; t < 2; t++)
{
swap(u, v);
int cur = get(u, c);
adj[u].push_back({v, w});
adj[u].push_back({cur, 0});
int cur1 = get(v, c);
adj[u].push_back({cur1, 0});
adj[cur].push_back({v, sum[cur] - w});
}
}
dijkstra();
if (d[n] > 1e15)
{
cout << -1;
}
else
{
cout << d[n];
}
}
