#include<bits/stdc++.h>
using namespace std;
int n, m;
int a, b, c, p;
vector< pair<int, pair<int,long long> > > v[100005];
map< pair<int,int> , vector< pair< pair<int,int>, long long > > > edg;
int cnt[200005]; long long sum[200005];
priority_queue< pair<long long, pair<int,int> > > pq;
map< pair<int,int>, long long > dis;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> a >> b >> c >> p;
v[a].push_back({b, {c, p} });
v[b].push_back({a, {c, p} });
}
for(int i=1; i<=n; i++) {
sort(v[i].begin(), v[i].end());
for(auto j:v[i]) {
cnt[j.second.first]++;
sum[j.second.first] += j.second.second;
}
for(auto j:v[i]) {
// case 1: direct
if(cnt[j.second.first] == 1)
edg[{i, 0}].push_back({{j.first, 0}, 0LL});
else
edg[{i, 0}].push_back({{j.first, 0}, j.second.second});
}
for(auto j:v[i]) {
edg[{j.first, 0}].push_back({{i, j.second.first}, 0});
edg[{i, j.second.first}].push_back({{j.first, 0}, sum[j.second.first]-j.second.second});
}
dis[{i, 0}] = 1e18;
for(auto j:v[i]) {
if(cnt[j.second.first] > 0) {
edg[{i, 0}].push_back({{i, j.second.first}, 0});
dis[{i, j.second.first}] = 1e18;
}
cnt[j.second.first] = sum[j.second.first] = 0;
}
}
dis[{1, 0}] = 0;
pq.push({0, {1, 0}});
while(!pq.empty()) {
auto curr = pq.top().second;
if(dis[curr] != -pq.top().first) {
pq.pop();
continue;
}
pq.pop();
if(curr == make_pair(n, 0)) {
cout << dis[curr] << "\n";
return 0;
}
for(auto j: edg[curr]) {
if(dis[curr] + j.second < dis[j.first]) {
dis[j.first] = dis[curr] + j.second;
pq.push({-dis[j.first], j.first});
}
}
}
cout << "-1\n";
}
