#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];
map<int, long long>ans[MX];
map<int, bool>seen[MX];
map<int, vector<int>>colored_edges[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);
colored_edges[u][c].push_back(i);
colored_edges[v][c].push_back(i);
}
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(seen[v].empty()) {
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)) 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)) ans[to][0] = INF;
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
} else if(seen[v][color[nerfed]]==0) {
seen[v][color[nerfed]] = 1;
for(auto e : colored_edges[v][color[nerfed]]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = cost[e] + ans[v][nerfed];
if(!ans[to].count(e)) 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)) 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(best, b.second);
}
if(best==INF) best = -1;
cout<<best<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
