#include <bits/stdc++.h>
#define int long long
struct Vert
{
int stop;
int cost;
int color;
int ind;
Vert() = default;
Vert(int stop, int cost, int color, int ind) : stop(stop), cost(cost), color(color), ind(ind) {};
};
signed
main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<std::map<int, std::vector<Vert>>> g(n);
for (int i = 0; i < m; i++)
{
int a, b;
int c, p;
std::cin >> a >> b >> c >> p;
a--, b--;
g[a][c].push_back(Vert(b, p, c, i));
g[b][c].push_back(Vert(a, p, c, i));
}
std::vector<std::map<int, int>> dist(n);
dist[0][-1] = 0;
std::set<std::pair<int, std::pair<int, int>>> s;
s.insert(std::make_pair(dist[0][-1], std::make_pair(0, -1)));
while (s.size() > 0)
{
auto v = s.begin()->second;
s.erase(s.begin());
if (v.second == -1)
{
std::map<int, int> all;
for (auto help : g[v.first])
{
for (auto now : help.second)
{
all[now.color] += now.cost;
}
}
for (auto help : g[v.first])
{
for (auto now : help.second)
{
int price = now.cost;
if (dist[now.stop].find(now.color) == dist[now.stop].end() ||
dist[now.stop][now.color] > dist[v.first][v.second])
{
s.erase(std::make_pair(dist[now.stop][now.color],
std::make_pair(now.stop, now.color)));
dist[now.stop][now.color] = dist[v.first][v.second];
s.insert(std::make_pair(dist[now.stop][now.color],
std::make_pair(now.stop, now.color)));
}
price = std::min(now.cost, all[now.color] - now.cost);
if (dist[now.stop].find(-1) == dist[now.stop].end() ||
dist[now.stop][-1] > dist[v.first][v.second] + price)
{
s.erase(std::make_pair(dist[now.stop][-1],
std::make_pair(now.stop, -1)));
dist[now.stop][-1] = dist[v.first][v.second] + price;
s.insert(std::make_pair(dist[now.stop][-1],
std::make_pair(now.stop, -1)));
}
}
}
}
else
{
std::map<int, int> all;
for (auto now : g[v.first][v.second])
{
all[now.color] += now.cost;
}
for (auto now : g[v.first][v.second])
{
int price = all[now.color] - now.cost;
if (dist[now.stop].find(-1) == dist[now.stop].end() || dist[now.stop][-1] > dist[v.first][v.second] + price)
{
s.erase(std::make_pair(dist[now.stop][-1],
std::make_pair(now.stop, -1)));
dist[now.stop][-1] = dist[v.first][v.second] + price;
s.insert(std::make_pair(dist[now.stop][-1],
std::make_pair(now.stop, -1)));
}
}
}
}
if (dist[n - 1].find(-1) == dist[n - 1].end())
{
std::cout << -1;
return 0;
}
std::cout << dist[n - 1][-1];
}
