#include<bits/stdc++.h>
using namespace std;
const int MX = 2e5 + 5;
const long long INF = 1e18;
vector<int>g[MX];
long long cost[MX], color[MX];
int edge[2][MX];
map<int,long long>sum[MX];
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=1; i<=m; ++i) {
int u, v, c, p;
cin>>u>>v>>c>>p;
color[i] = c, cost[i] = p;
edge[0][i] = u, edge[1][i] = v;
sum[u][c] += p;
sum[v][c] += p;
g[u].push_back(i);
g[v].push_back(i);
}
for(int i=1; i<=n; ++i) {
sort(g[i].begin(), g[i].end());
}
vector<vector<long long>>ans(n+1, vector<long long>(1, INF));
vector<vector<bool>>vis(n+1, vector<bool>(1, false));
for(int i=1; i<=m; ++i) {
ans[edge[0][i]].push_back(INF);
ans[edge[1][i]].push_back(INF);
vis[edge[0][i]].push_back(false);
vis[edge[1][i]].push_back(false);
}
priority_queue<tuple<long long, int, int>>pq;
pq.emplace(0, 1, 0);
ans[1][0] = 0;
while(!pq.empty()) {
int v = get<1>(pq.top());
int id = get<2>(pq.top());
int nerfed = -1;
if(id) nerfed = g[v][id-1];
pq.pop();
if(vis[v][id]) continue;
vis[v][id] = 1;
for(auto e : g[v]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = cost[e] + ans[v][id];
int nextID = lower_bound(g[to].begin(), g[to].end(), e) - g[to].begin()+1;
if(ans[to][nextID]>cur) {
ans[to][nextID] = cur;
pq.emplace(-cur, to, nextID);
}
cur = sum[v][color[e]] - cost[e] + ans[v][id];
if(nerfed!=-1 && color[nerfed]==color[e]) cur -= cost[nerfed];
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
}
long long best = INF;
for(auto b : ans[n]) {
best = min(b, best);
}
if(best==INF) best = -1;
cout<<best<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
