//直接抄解，因為我笨
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fs first
#define sc second
int n, m;
int vis[510000] = {0}, dis[510000];
vector< pair<int,pii> > e[510000];
vector< pii > ne[510000];
signed main () {
//輸入
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c, k;
cin >> a >> b >> c >> k;
e[a] . push_back({c,{b,k}});
e[b] . push_back({c,{a,k}});
}
//建圖
int now = n + 1;
for (int i = 1; i <= n; i++) {
//操作1
for (auto [c, p] : e[i]) ne[i] . push_back(p);
//操作2、先操作1再操作2
map<int, vector<pii>>mp;
for (auto [c, p] : e[i]) mp[c] . push_back(p);
for (auto [c, vv] : mp) {
++now;
int sum = 0;
for (auto [j, w] : vv) sum += w;
for (auto [j, w] : vv) {
//操作2
ne[i] . push_back({j, sum - w});
//先1再2
ne[now] . push_back({j, sum - w});
ne[j] . push_back({now, 0});
}
}
}
// Dijkstra and output
memset(dis, 63, sizeof(dis));
int inf = dis[0];
dis[1] = 0;
priority_queue< pii, vector<pii>, greater<pii> > pq;
pq.push({0, 1});
while (pq.size()) {
auto [wow, i] = pq.top();
pq.pop();
if (vis[i]) continue;
vis[i] = 1;
for (auto [j, w] : ne[i]) {
if (dis[i] + w < dis[j]) {
dis[j] = dis[i] + w;
pq.push({dis[j], j});
}
}
}
if (dis[n] >= inf / 2) dis[n] = -1;
cout << dis[n] << '\n';
}
