#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const long long INF = 1e18;
struct ToEdge
{
int v;
long long p;
ToEdge(int v = 0, long long p = 0) : v(v), 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];
map <int, int> 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;
Adj[u][c].emplace_back(v, p);
Adj[v][c].emplace_back(u, 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 : Adj[node])
{
for(auto y : x.second)
{
Add(dist, y.v, x.first);
Add(dist + min(y.p, Sum[node][x.first] - y.p), y.v, 0);
}
}
}
else
{
for(auto x : Adj[node][color])
{
Add(dist + Sum[node][color] - x.p, x.v, 0);
}
}
}
}
if(Dist[n][0] == INF)
{
Dist[n][0] = -1;
}
cout << Dist[n][0] << '\n';
}
