#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<ll,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 105;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};
int n, m;
map<int,vector<iii>> g[N];
ll dp[N];
map<int,ll> dp2[N], sum[N];
// Giả sử ta đi trên đường u -> v -> k, dp2 là trường hợp mà thay vì đổi
// màu cạnh u -> v thì ta đổi màu các cạnh có cùng màu với cạnh u -> v
// nối với đỉnh v, khi đó, ta cũng xét cả th mà ta đổi cạnh kề v
// (chứa của u -> v) nhưng không đổi cạnh v -> k
// (màu v -> k == màu u -> v)
void dijk(int beg)
{
priority_queue<iii,vector<iii>,greater<iii>> pq;
pq.push({0,{1,0}});
FOR(i,1,n) dp[i] = INF;
dp[beg] = 0;
while(!pq.empty())
{
int u = pq.top().se.fi;
ll cost = pq.top().fi;
int c = pq.top().se.se;
pq.pop();
if(c)
{
if(cost > dp2[u][c]) continue;
for(auto H : g[u][c])
{
int v = H.fi;
ll l = H.se.se;
ll newcost = cost + sum[u][c] - l;
if(newcost < dp[v])
{
dp[v] = newcost;
pq.push({dp[v],{v,0}});
}
}
}
else
{
if(cost > dp[u]) continue;
for(auto &graph : g[u])
{
for(auto H : graph.se)
{
int v = H.fi;
int c = H.se.fi;
ll l = H.se.se;
ll case1 = cost + l; // đổi màu cạnh H
if(case1 < dp[v])
{
dp[v] = case1;
pq.push({dp[v],{v,0}});
}
ll case2 = cost + sum[u][c] - l;
// đổi màu các cạnh khác H cùng màu với H.
if(case2 < dp[v])
{
dp[v] = case2;
pq.push({dp[v],{v,0}});
}
ll case3 = cost; // đổi ở v.
if(!dp2[v].count(c) || case3 < dp2[v][c])
{
dp2[v][c] = case3;
pq.push({dp2[v][c],{v,c}});
}
}
}
}
}
}
void solve()
{
dijk(1);
cout << (dp[n] >= INF ? -1 : dp[n]);
}
void input()
{
//freopen("TEST.INP", "r", stdin);
//freopen("TEST.OUT", "w", stdout);
cin >> n >> m;
FOR(i,1,m)
{
int u, v, c, d;
cin >> u >> v >> c >> d;
g[u][c].pb({v,{c,d}});
g[v][c].pb({u,{c,d}});
sum[u][c] += d;
sum[v][c] += d;
}
}
signed main()
{
faster
input();
solve();
}
