#include <bits/stdc++.h>
#define ll long long
const int MAXN = 1e5 + 10;
const int MAXM = 2e5 + 10;
const ll inf = 1e18 + 10LL;
using namespace std;
int N, M;
int color[MAXM * 2];
int j[MAXM * 2];
ll p[MAXM * 2];
map<pair<int, int>, ll> cost;
map<pair<int, int>, int> key;
vector<int> adj[MAXN];
vector<pair<int, ll>> graph[MAXM * 3];
void add(pair<int, int> nodeInf, ll val)
{
if (cost.find(nodeInf) == cost.end())
cost[nodeInf] = 0;
cost[nodeInf] += val;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0, a, b; i < 2 * M; i += 2)
{
cin >> a >> b >> color[i] >> p[i];
j[i] = b;
j[i + 1] = a;
color[i + 1] = color[i];
p[i + 1] = p[i];
add(make_pair(a, color[i]), p[i]);
add(make_pair(b, color[i]), p[i]);
key[make_pair(a, color[i])] = key[make_pair(b, color[i])] = 0;
adj[a].push_back(i);
adj[b].push_back(i + 1);
}
for (int i = 1; i <= N; i++)
key[make_pair(i, 0)] = 0;
int Key = 0;
for (auto &e : key)
e.second = ++Key;
for (int i = 1; i <= N; i++)
{
int x = key[make_pair(i, 0)];
for (auto e : adj[i])
{
int y = key[make_pair(i, color[e])];
int a = key[make_pair(j[e], 0)];
int b = key[make_pair(j[e], color[e])];
graph[a].push_back(make_pair(y, cost[make_pair(i, color[e])] - p[e]));
graph[b].push_back(make_pair(x, 0));
graph[a].push_back(make_pair(x, p[e]));
}
}
for (auto e : key)
if (e.first.second)
graph[e.second].push_back(make_pair(key[make_pair(e.first.first, 0)], 0));
vector<ll> dist(Key + 1, inf);
int T = key[make_pair(N, 0)];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push(make_pair(dist[T] = 0, T));
while (!pq.empty())
{
int x = pq.top().second;
ll d = pq.top().first;
pq.pop();
if (d != dist[x])
continue;
for (auto e : graph[x])
{
ll newD = d + e.second;
int node = e.first;
if (newD >= dist[node])
continue;
pq.push(make_pair(dist[node] = newD, node));
}
}
int S = key[make_pair(1, 0)];
if (dist[S] == inf)
dist[S] = -1;
cout << dist[S] << "\n";
}
