#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int MX = 2e5 + 5;
const long long INF = 1e18;
vector<int>g[MX/2];
int cost[MX], color[MX];
int edge[2][MX];
map<int,vector<int>>colored_edges[MX/2];
bool atall[MX/2];
map<int,bool>seen[MX/2];
map<int, long long>ans[MX/2], sum[MX/2];
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=1, u,v,p,c; i<=m; ++i) {
cin>>u>>v>>c>>p;
g[u].push_back(i);
g[v].push_back(i);
color[i] = c, cost[i] = p;
edge[0][i] = u, edge[1][i] = v;
colored_edges[u][c].push_back(i);
colored_edges[v][c].push_back(i);
sum[v][c] += p;
sum[u][c] += p;
}
priority_queue<tuple<long long, int, int>>pq;
pq.emplace(0, 1, 0);
ans[1][0] = 0;
while(!pq.empty()) {
int v, nerfed;
long long c;
tie(c, v, nerfed) = pq.top();
pq.pop();
if(ans[v][nerfed]!=-c) continue;
//cerr<<v<<' '<<nerfed<<" "<<c<<" "<<ans[v][nerfed]<<endl;
if(nerfed) {
for(auto e : colored_edges[v][nerfed]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = ans[v][nerfed] + sum[v][nerfed] - cost[e];
if(ans[to].count(0)==0) ans[to][0] = INF;
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
} else {
for(auto e : g[v]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = ans[v][nerfed] + sum[v][color[e]] - cost[e];
if(ans[to].count(0)==0) ans[to][0] = INF;
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
cur = ans[v][nerfed];
if(ans[to].count(color[e])==0) ans[to][color[e]] = INF;
if(ans[to][color[e]]>cur) {
ans[to][color[e]] = cur;
pq.emplace(-cur, to, color[e]);
}
cur = ans[v][nerfed] + cost[e];
if(ans[to].count(0)==0) ans[to][0] = INF;
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
}
}
if(ans[n].count(0)==0) ans[n][0] = INF;
long long best = ans[n][0];
if(best==INF) best = -1;
cout<<best<<'\n';
}
int main() {
ios_base::sync_with_stdio();
cin.tie(nullptr);
PlayGround();
//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
