#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1<<18;
vector<pair<int,int>> nei[N];
int b[N], a[N], p[N], inf = 1e17;
map<int,int> dp[N], Sum[N];
void dijkstra(){
for (int i=2;i < N;i++)
dp[i][0] = inf;
dp[1][0] = 0;
set<pair<int,pair<int,int>>> st = {{0, {1, 0}}};
while (st.size() > 0){
auto [mn, pr] = *st.begin();
auto [u, cl] = pr;
st.erase(begin(st));
if (mn != dp[u][cl])
continue;
if (cl == 0){
for (auto [col, id] : nei[u]){
int i = b[id] + a[id] - u;
if (i == u)
continue;
if (i != u and dp[i][0] > dp[u][0] + min(p[id], Sum[u][col] - p[id]))
dp[i][0] = dp[u][0] + min(p[id], Sum[u][col] - p[id]), st.insert({dp[i][0], {i, 0}});
if (i != u and dp[i][col] > dp[u][0])
dp[i][col] = dp[u][0], st.insert({dp[i][col], {i, col}});
}
continue;
}
int ub = upper_bound(begin(nei[u]), end(nei[u]), make_pair(cl, -cl)) - begin(nei[u]);
for (; ub < nei[u].size() and nei[u][ub].first == cl;ub++){
auto [col, id] = nei[u][ub];
int i = b[id] + a[id] - u;
if (i != u and dp[i][0] > dp[u][cl] + Sum[u][cl] - p[id])
dp[i][0] = dp[u][cl] + Sum[u][cl] - p[id], st.insert({dp[i][0], {i, 0}});
}
}
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
cin>>n>>m;
for (int i=1, c;i<=m;i++){
cin>>a[i]>>b[i]>>c>>p[i];
nei[a[i]].push_back({c, i});
nei[b[i]].push_back({c, i});
Sum[a[i]][c] += p[i];
Sum[b[i]][c] += p[i];
dp[ a[i]][c] = dp[b[i]][c] = inf;
}
for (int i=1;i<=n;i++)
sort(begin(nei[i]), end(nei[i]));
dijkstra();
if (dp[n][0] == inf)
dp[n][0] = -1;
cout<<dp[n][0]<<'\n';
}
