#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const long long INF = 1e18;
struct ToEdge
{
int v, c;
long long p;
ToEdge(int v = 0, int c = 0, long long p = 0) : v(v), c(c), p(p) {}
};
priority_queue <tuple <long long, int, int>, vector <tuple <long long, int, int> >, greater <tuple <long long, int, int> > > pq;
int n, m;
long long p[MAXN];
vector <ToEdge> E[MAXN];
map <int, long long> Sum[MAXN];
map <int, vector <ToEdge> > Adj[MAXN];
map <int, long long> Dist[MAXN];
void Add(long long dist, int node, int color)
{
if(Dist[node][color] > dist)
{
Dist[node][color] = dist;
pq.push(make_tuple(dist, node, color));
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u, v, c;
long long p;
cin >> u >> v >> c >> p;
E[u].emplace_back(v, c, p);
E[v].emplace_back(u, c, p);
Adj[u][c].emplace_back(v, c, p);
Adj[v][c].emplace_back(u, c, p);
Dist[u][c] = INF;
Dist[v][c] = INF;
Sum[u][c] += p;
Sum[v][c] += p;
}
for(int i = 1; i <= n; i++)
{
Dist[i][0] = INF;
}
Add(0, 1, 0);
while(pq.empty() == false)
{
int node, color;
long long dist;
tie(dist, node, color) = pq.top();
pq.pop();
if(dist == Dist[node][color])
{
if(color == 0)
{
for(auto x : E[node])
{
Add(dist, x.v, x.c);
Add(dist + min(Sum[node][x.c] - x.p, x.p), x.v, 0);
assert(Sum[node][x.c] - x.p >= 0);
}
}
else
{
for(auto x : Adj[node][color])
{
Add(dist + Sum[node][color] - x.p, x.v, 0);
assert(Sum[node][color] - x.p >= 0);
}
}
}
}
if(Dist[n][0] == INF)
{
Dist[n][0] = -1;
}
cout << Dist[n][0] << '\n';
}
