#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<array<int, 3>> adj[100005];
ll cost[100005];
bool visited[100005];
unordered_map<int, array<ll, 2>> s[100005]; // didnt change road, changed road
int main()
{
cin.tie(NULL) -> sync_with_stdio(false);
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; ++i)
cost[i] = LLONG_MAX;
for (int i = 0; i < M; ++i)
{
int a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].push_back({b, c, p});
adj[b].push_back({a, c, p});
}
using T = array<ll, 2>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 1});
while (!pq.empty())
{
auto [curcost, node] = pq.top();
pq.pop();
if (visited[node])
continue;
visited[node] = true;
unordered_map<int, array<ll, 2>> m; // sum, best option
for (auto& [i, c, p] : adj[node])
m[c][1] = curcost;
for (auto& [i, c, p] : adj[node])
{
m[c][0] += p;
if (visited[i])
m[c][1] = min(m[c][1], s[i][node][1] - p);
}
for (auto& [i, c, p] : adj[node])
{
if (visited[i])
continue;
s[node][i][0] = m[c][1] + m[c][0] - p;
s[node][i][1] = curcost + p;
ll next = min(s[node][i][0], s[node][i][1]);
if (next < cost[i])
pq.push({cost[i] = next, i});
}
}
cout << (cost[N] == LLONG_MAX ? -1 : cost[N]) << endl;
return 0;
}
