#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define f first
#define s second
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define ii pair <int,int>
#define pii pair <ll,ll>
#define all(x) x.begin(),x.end()
const int N = 1e5;
const ll oo = 1e18;
struct Edge
{
int v; ll p;
int tp;
};
map <int, vector <Edge>> g[N + 5];
map <int,ll> dp2[N + 5], psum[N + 5];
ll dp[N + 5];
int main()
{
FastIO
int n,m;
cin >> n >> m;
FOR(i,1,m)
{
int a,b,c,p;
cin >> a >> b >> c >> p;
g[a][c].push_back({b,p,c});
g[b][c].push_back({a,p,c});
psum[a][c] += p;
psum[b][c] += p;
}
FOR(i,1,n) dp[i] = oo;
dp[1] = 0;
priority_queue <tuple <ll, int , int>> q;
q.push({0,1,0});
while (!q.empty()) {
ll cost, node, c;
tie(cost, node, c) = q.top();
q.pop();
if (c) {
for (Edge j : g[node][c]) {
ll case1 = psum[node][c] - j.p - cost;
if (case1 < dp[j.v]) {
dp[j.v] = case1;
q.push({-dp[j.v], j.v, 0});
}
}
}
else {
if (dp[node] != -cost) continue;
for (auto i : g[node]) {
for (Edge j : i.s) {
// Don't pick j, change j's neighbour.
ll case1 = psum[node][j.tp] - j.p - cost;
if (case1 < dp[j.v]) {
dp[j.v] = case1;
q.push({-dp[j.v], j.v, 0});
}
// Pick j & not change its neighbor.
ll case2 = j.p - cost;
if (case2 < dp[j.v]) {
dp[j.v] = case2;
q.push({-dp[j.v], j.v, 0});
}
// Pick j & change its neighbor.
ll case3 = -cost;
if (!dp2[j.v][j.tp] || case3 < dp2[j.v][j.tp]) {
dp2[j.v][j.tp] = case3;
q.push({-dp2[j.v][j.tp], j.v, j.tp});
}
}
}
}
}
if (dp[n] != oo) cout << dp[n];
else cout << -1;
}
