#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 = get<1>(pq.top());
int nerfed = get<2>(pq.top());
pq.pop();
if(atall[v]==0) {
atall[v] = 1;
if(nerfed) seen[v][color[nerfed]] = 1;
for(auto e : g[v]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = cost[e] + ans[v][nerfed];
if(ans[to].count(e)==0) ans[to][e] = INF;
if(ans[to][e]>cur) {
ans[to][e] = cur;
pq.emplace(-cur, to, e);
}
cur = sum[v][color[e]] - cost[e] + ans[v][nerfed];
if(nerfed!=e && color[nerfed]==color[e]) cur -= cost[nerfed];
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 if(nerfed && !seen[v].count(color[nerfed])) {
seen[v][color[nerfed]] = 1;
for(auto e : colored_edges[v][color[nerfed]]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = sum[v][color[e]] - cost[e] + ans[v][nerfed];
if(nerfed!=e && color[nerfed]==color[e]) cur -= cost[nerfed];
if(ans[to].count(0)==0) ans[to][0] = INF;
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.second, best);
}
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;
}
