#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define int long long
const int N = 1<<18;
vector<pair<int,int>> nei[N];
int c[N], p[N], inf = 1e17;
map<int,int> dp[N>>1], Sum[N>>1];
void dijkstra(int u){
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;
for (auto [i, id] : nei[u]){
if (cl != 0 and c[id] != cl)
continue;
// int v1 = mn, v2 = dp[i][cl], v3 = dp[i][0], v4 = Sum[u][cl];
if (cl == 0){
if (dp[i][0] > dp[u][0] + min(p[id], Sum[u][c[id]] - p[id]))
dp[i][0] = dp[u][0] + min(p[id], Sum[u][c[id]] - p[id]), st.insert({dp[i][0], {i, 0}});
if (dp[i][c[id]] > dp[u][0])
dp[i][c[id]] = dp[u][0], st.insert({dp[i][c[id]], {i, c[id]}});
}
else{
if (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, a, b;i<=m;i++){
cin>>a>>b>>c[i]>>p[i];
nei[a].push_back({b, i});
nei[b].push_back({a, i});
Sum[a][c[i]] += p[i];
Sum[b][c[i]] += p[i];
dp[ a][c[i]] = dp[b][c[i]] = inf;
}
dijkstra(1);
if (dp[n][0] == inf)
dp[n][0] = -1;
cout<<dp[n][0]<<'\n';
}
