#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i=(a), _b=(b); i<=_b; i++)
#define FORD(i, a, b) for(int i=(a), _b=(b); i>=_b; i--)
#define BIT(i, j) ((i>>j)&1)
#define pb push_back
#define ii pair<ll, ll>
#define pii pair<ll, ii>
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const ll inf = 1e18;
const ll mod = 1e9+7;
const ll N = 200005;
const ll M = 50005;
int n, m;
vector <tuple <int, int, ll>> adj[N];
priority_queue<ii, vector<ii>, greater<ii>> pq;
ll f[N], color[N], sum[N];
void dijkstra ()
{
fill (f + 1, f + n + 1, inf);
pq.push({0, 1});
f[1] = 0;
while (!pq.empty())
{
auto [val, u] = pq.top();
pq.pop();
if (u == n)
{
cout << val;
return;
}
if (val != f[u]) continue;
for (auto [v, c, cost] : adj[u])
{
color[c] = inf;
sum[c] = 0;
}
for (auto [v, c, cost] : adj[u])
{
color[c] = min(color[c], f[v]);
sum[c] += cost;
}
for (auto [v, c, cost] : adj[u])
{
ll dd = min({val + cost, val + sum[c] - cost, color[c] + sum[c] - cost});
if (f[v] > dd)
{
f[v] = dd;
pq.push({f[v], v});
}
}
}
cout << -1;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
adj[a].emplace_back(b, c, p);
adj[b].emplace_back(a, c, p);
}
dijkstra();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "robot1"
if(fopen(task".inp", "r"))
{
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
if(fopen("task.inp", "r"))
{
freopen("task.INP", "r", stdin);
freopen("task.OUT", "w", stdout);
}
solve();
return 0;
}
